Binary subtrees with few labeled paths (Q654001)

If \(T\) is a complete ternary tree of depth \(n\), let \({\mathcal{B}}(T)\) to be the set of all binary subtrees of \(T\) that are complete with depth \(n\). A tree \(T\) is said to be edge-labeled if each edge in \(T\) is assigned a label from the set \(\{0,1\}\). Let \({\mathcal{T}}_{n}\) be the set of all ternary, complete, edge-labeled trees of depth \(n\). If \(T \in {\mathcal{T}}_{n}\), \(r\) is the root of \(T\), and \(\sigma \) is a leaf in \(T\), then reading the elements along the path from \( r\) to \(\sigma\) in \(T\) gives a path-label \(x \in \{0,1\}^{n}\), and it is said that \(\sigma\) has path-label \(x\). Let \(L(T)\) to be the set of all path-labels in \(T\). For each \(T \in {\mathcal{T}}_{n}\), let \(f(T) = \min\{| L(S)| : S\in {\mathcal{B}}(T)\}\), and for each \(n\), let \(f(n) = \max\{f(T): T\in {\mathcal{T}}_{n}\}\). The purpose of this paper is to study the behavior of \(f(n)\) as \(n \rightarrow \infty\). It is shown that \(f(n) \geq 2^{(n-3)/\log_{2}3}\), \(\lim_{n\rightarrow \infty}(f(n))^{1/n}\) exists and this limit has a value between \(2^{1/\log_{2 }3}\) and 2. Also, if \(c<\sqrt{\log_{2}(4/3)}\), then there is a constant \(\gamma\) such that \( f(n)\leq \gamma 2^{n-c\sqrt{n}}\). Consequently, the ratio \(f(n)/2^{n}\) tends to zero as \(n\) grows. The following Ramsey interpretation is deduced: for large \(n\), every edge-labeled complete ternary tree of depth \(n\) admits a complete binary subtree of depth \( n\) whose path-labels constitute an arbitrarily small fraction of the space of all possible path-labels. These results lead to a solution of a problem in computability theory and effective randomness: the class of Kurtz random reals is not Medvedev reducible to \( DNR_{3}\).