2
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pablo Dec 22 '14 at 7:31
  • $\begingroup$ 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. $\endgroup$ – Bjørn Kjos-Hanssen Dec 22 '14 at 7:41
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Dec 22 '14 at 0:31
  • $\begingroup$ Oops, you're right! $\endgroup$ – Peva Blanchard Dec 22 '14 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.