Binary subtrees with few path labels
by
Kevin Milans
University of Illinois at Urbana-Champaign
Coauthors: Rod Downey, Noam Greenberg, and Carl Jockusch

A rooted tree is k-ary if all non-leaves have k children; it is complete if all leaves are at the same distance from the root. Let T be the complete ternary tree of depth n. If each edge in T is labeled 0 or 1, then the labels along the edges of a path from the root to a leaf form a "path label" in {0, 1}ⁿ. Let f(n) be the maximum, over all edge-labeled complete ternary trees T of depth n, of the minimum number of distinct path labels on a complete binary subtree of depth n.

The problem of bounding f(n) arose in a problem in computability theory, where it was hoped that f(n)/2ⁿ tends to 0 as n grows. This is true; we show that f(n)/2ⁿ is O(2^{-c √n}) for a positive constant c. From below, we show that f(n) ≥ (1.548)ⁿ for sufficiently large n.

Date received: May 1, 2009