# Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:

1. $G$ has no complete subtrees (the graph below any vertex of $G$ is not a complete binary tree).

2. There exists some $\epsilon > 0$ such that for any $n \in \mathbb{N}$ the number of vertices of $G$ whose distance from the root is $n$ is at least $\epsilon2^n$.

Yes. In fact you can take the tree corresponding to all sequences $x$ of 0s and 1s such that the fraction of 1s is no more than 2/3.

• This is a good idea. The problem is that even though 1 and 2 are satisfied, I do not see why this set of sequences can be obtained by removing subtrees as I required. What you can get by removing subtrees, is the set of sequences with every prefix having at most 2/3 1s. In this case, is 2 satisfied? Dec 22 '14 at 7:31
• Yes, implicitly I meant that (see version before I edited the answer if you can). And yes, 2 is satisfied. Take a look at the proof of the strong law of large numbers to see why. Dec 22 '14 at 7:41

I don't know if it will help you, but there is another reformulation that may be useful here.

You can model the infinite complete binary tree $\{0,1\}^{\omega}$ by the interval $[0,1]$ (with the binary expansion). In particular, if you fix a finite binary string $x$, then the subtree consisting of the branch $x$ followed by a complete binary tree represents a subinterval of $[0,1]$ of length $2^{-|x|}$.

So finding a subtree satisfying your condition 1 amounts to finding a subset of $[0,1]$ with (Lebesgue) measure zero closed subset with empty interior (thanks Blass).

The condition 2 is related to Hausdorff dimension of subsets of $[0,1]$. Indeed, the collection of vertices at distance $n$ from the root can be seen as a collection of subintervals, each of length $2^{-n}$, whose union covers your subset. The number of vertices is then the number of such intervals.

Roughly speaking, if you take a subset of dimension $\theta$ (Hausdorff or a variant, I don't remember exactly), then the number of vertices of your subtree at distance $n$ grows like $O(\theta^n)$ when $n \rightarrow \infty$.

pb

• In the $[0,1]$ model, condition 1 requires the set to be a closed set with empty interior, but it can still have positive Lebesgue measure. Dec 22 '14 at 0:31
• Oops, you're right! Dec 22 '14 at 0:57