Paths vs. stars in the local profile of trees

Abstract

The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees. For a tree $T$, let $p_1^{(k)}(T)$ be the proportion of paths among all $k$-vertex subtrees (induced connected subgraphs) of $T$, and let $p_2^{(k)}(T)$ be the proportion of stars. Our main theorem states: if $p_1^{(k)}(T_n)\to 0$ for a sequence of trees $T_1,T_2,\dots$ whose size tends to infinity, then $p_2^{(k)}(T_n)\to 1$. Both are also shown to be equivalent to the statement that the number of $k$-vertex subtrees grows superlinearly and the statement that the $(k-1)$th degree moment grows superlinearly.