5
$\begingroup$

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

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

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<n/a$.

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<a(1-n_1/n)$. 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.$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DmitryZ Mar 30 at 12:27
  • $\begingroup$ @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. $\endgroup$ – domotorp Mar 30 at 14:37
  • $\begingroup$ 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! $\endgroup$ – DmitryZ Mar 31 at 11:29
  • $\begingroup$ @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. $\endgroup$ – domotorp Mar 31 at 12:23
  • $\begingroup$ 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? $\endgroup$ – DmitryZ Mar 31 at 17:48

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.