Binary subtrees with few labeled paths
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}\).
- Algorithmic randomness and complexity.
- An Effective Version of Dilworth's Theorem
- Calibrating Randomness
- Diagonally non-recursive functions and effective Hausdorff dimension
- Difference sets and inverting the difference operator
- Functional iteration and the Josephus problem
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Mass Problems and Randomness
- On the Equimorphism Types of Linear Orderings
- The canonical Ramsey theorem and computability theory
- The McKinsey axiom is not canonical
- The Medvedev lattice of computably closed sets
- On the uniform computational content of computability theory
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Diagonally non-computable functions and bi-immunity
- scientific article; zbMATH DE number 5016713 (Why is no real title available?)
- Weihrauch Complexity in Computable Analysis
- Forcing with bushy trees
- The coding power of a product of partitions
- Growth and irreducibility in path-incompressible trees
- Ramsey-Collatz correlation and some extremal combinatorics, along with Ramsey-Mahler rare concurrencies
This page was built for publication: Binary subtrees with few labeled paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q654001)
