Binary subtrees with few path labels

Combinatorics Seminar
Thursday, October 14, 2010 - 11:05
1 hour (actually 50 minutes)
Skiles 114
University of South Carolina
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.