Georgia Institute of Technology College of Sciences

A rooted tree is _k-ary_ if all non-leaves have k children; it is_complete_ if all leaves have the same distance from the root. Let T bethe complete ternary tree of depth n. If each edge in T is labeled 0 or1, then the labels along the edges of a path from the root to a leafform a "path label" in {0,1}^n. Let f(n) be the maximum, over all{0,1}-edge-labeled complete ternary trees T with depth n, of the minimumnumber of distinct path labels on a complete binary subtree of depth nin T.The problem of bounding f(n) arose in studying a problem incomputability theory, where it was hoped that f(n)/2^n tends to 0 as ngrows. This is true; we show that f(n)/2^n is O(2^{-c \sqrt(n)}) forsome positive constant c. From below, we show that f(n) >= (1.548)^nfor sufficiently large n. This is joint work with Rod Downey, NoamGreenberg, and Carl Jockusch.