Originator: Rod Downey, Noam Greenberg, Carl Jockusch, and Kevin Milans (presented by Kevin Milans - REGS 2008)
Definitions: A k-ary tree is a rooted tree in which all non-leaves have k children. A binary tree is a 2-tree; a ternary tree is a 3-ary tree. A complete k-ary tree is a k-ary tree in which all leaves have the same distance from the root (also called a perfect k-ary tree in this subject). That common distance is the depth of the tree.
Let T be a complete ternary tree of depth n in which each edge is labeled with 0 or 1. Reading the edge-labels along a path in T from the root to a leaf yields a path-label in {0,1}n. Let f(T) be the minimum, over all complete binary subtrees of T with depth n, of the number of path-labels occurring in the subtree. Let f(n) to be the maximum of f(T) such that T is a {0,1}-edge-labeled complete ternary tree of depth n.
Background: Understanding the asymptotic behavior of f(n) will be helpful in resolving a question in computability theory. It is known that 2(n-3)/lg3 ≤ f(n) ≤ a2n - b√n, where a and b are positive constants. Consequently, f(n)/2n→0 and 21/lg3≤limn→∞f(n)1/n≤2. The lower bound is about 1.548.
Question 1: What is limn→∞f(n)1/n? Is it less than 2?
Comments: The existence of the limit follows from the observation that always f(r+s) ≥ f(r)f(s). The lower bound on f(n) comes from an explicit construction. The proof of the upper bound uses the probabilistic method to construct a large family of sets with desired properties and uses the family to iteratively find and extend a 2-ary subtree with few path labels. The value of f(n) is n for n≤4, but 6≤f(5)≤8.
Question 2: For fixed n, does there exist a tree T maximizing f(T) such that no vertex has three edges of the same color to its children? What is the expected value of f(T) for a tree T of depth n with a random 0,1-assignment on its edges?
References:
R. Downey, N. Greenberg, C. Jockusch, and K. Milans,
Binary subtrees with few path labels,
slide presentation.