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:
$G$ has no complete subtrees (the graph below any vertex of $G$ is not a complete binary tree).
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.
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
