pith. sign in

arxiv: 1512.06526 · v2 · pith:BA7HIZJGnew · submitted 2015-12-21 · 🧮 math.CO

Paths vs. stars in the local profile of trees

classification 🧮 math.CO
keywords treesgrowslocalpathsprofileproportionstarsstatement
0
0 comments X
read the original 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^{(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) \to 0$ for a sequence of trees $T_1,T_2,\ldots$ whose size tends to infinity, then $p^{(k)}_2(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.