Paths vs. stars in the local profile of trees (Q510335): Difference between revisions

Summary: The aim of this paper is to provide an affirmative answer to a recent question by \textit{S. Bubeck} and \textit{N. Linial} [J. Graph Theory 81, No. 2, 109--119 (2016; Zbl 1330.05037)] on the local profile of trees. For a tree \(T\), let \(p^{(k)}_1(T)\) be the proportion of paths among all \(k\)-vertex subtrees (induced connected subgraphs) of \(T\), and let \(p^{(k)}_2(T)\) be the proportion of stars. Our main theorem states: if \(p^{(k)}_1(T_n) \rightarrow 0\) for a sequence of trees \(T_1,T_2,\ldots\) whose size tends to infinity, then \(p^{(k)}_2(T_n) \rightarrow 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.