# Does a bounded branching/log depth dihotomy hold for rooted trees?

Let $$T$$ be a rooted tree. For any subtree $$T' \subset T$$ write $$L(T')$$ for the number of leaves of $$T'$$.

Further, for $$T' \subset T$$ define the branch-depth of a node $$v \in T'$$ as the number of nodes $$w$$ on the path from $$v$$ to $$root(T')$$ having more than a single child. The branch depth of $$T'$$ is then the maximal branch-depth of its leaves.

Let's call a tree binary if each node has at most two children.

I wonder if something along the following lines is true. There is constant $$c > 0$$ such that for any tree $$T$$ with $$N$$ leaves there is a subtree $$T$$ with $$L(T) \geq N^{c}$$ which is either binary or has branch-depth $$O(\log N)$$.

• Perhaps this sort of argument can help mathoverflow.net/questions/280505/… Mar 22 '19 at 13:29
• Is the branch-depth of a tree the maximum branch-depth of a vertex, or the minimum? Mar 28 '19 at 12:54
• Thanks for the comment! It's the maximum over the leaves, edited the question. Mar 28 '19 at 15:50
• Edited the conjecture into a more uniform statement Mar 28 '19 at 16:09
• By binary tree, do you mean that every node should have at most two children? Mar 29 '19 at 8:17

Call a tree on $$x$$ vertices low if its branch-depth is at most $$\log x$$.

We prove by induction that for every tree on $$n$$ vertices there are some numbers $$a,b$$ such that $$n\le ab$$ and the tree contains a binary subtree on $$a$$ vertices AND a low subtree on $$b$$ vertices. Suppose this is false for some $$n$$, and denote the size of its largest binary subtree by $$a$$. Denote the sizes of the trees we obtain after deleting the root by $$n_1,n_2,\ldots$$, so $$\sum n_i=n-1$$. By induction, in the $$i$$'th subtree we have a binary tree on $$a_i\le a$$ vertices and a low subtree on $$b_i$$ vertices for some $$n_i/a_i\ge b_i.

Now fix some index, say 1. Merging the largest binary subtrees of the first and $$i$$-th tree would give a binary tree of size $$a_1+a_i+1\le a$$. Since $$a_1>an_1/n$$, this gives $$a_i. Let us see what happens if we merge the low subtrees on $$b_i$$ vertices. The branch-depth of the new subtree is $$\max_i b_i+1$$, and it has $$1+\sum_i b_i$$ vertices. If we can show that $$1+\sum_i b_i\ge 2b_1$$, then we know that this new subtree is also low and we are done as $$1+\sum_i b_i\ge 1+\sum n_i/a\ge n/a$$. But $$1+\sum_i b_i\ge 2b_1$$ holds, as

$$\sum_{i>1} b_i\ge \sum n_i/a_i>\sum n_i/(a(1-n_1/n))=(n-n_1)/(a(1-n_1/n))=n/a>b_i.$$

• I’m not sure I follow the step when the root is deleted. Note that in the conjecture the “size” $L(T)$ is not the number of vertices but the number of leaves. Mar 30 '19 at 12:27
• @DmitryZ Right, vertices should read as leafs throughout my answer, and ignore a few $\pm 1$'s. Why is the deletion of the root not clear? After you delete it, the tree falls apart to smaller trees. Mar 30 '19 at 14:37
• Gotcha. I was confused by +/- 1ones, but modulo minor (I believe there should be $max_i \log b_i$) edits I think the argument is correct! Mar 31 '19 at 11:29
• @DmitryZ Indeed, you're right about that too! I can see that you've accepted my answer, maybe you've forgotten that you have to award the bounty separately. Mar 31 '19 at 12:23
• Oh, thanks didn't now I have to approve the bounty. Many thanks for your answer. Btw, how would like to be credited if your argument (perhaps in some slightly different form) will be included in a paper? Mar 31 '19 at 17:48