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.
@article{10_37236_5943,
author = {\'Eva Czabarka and L\'aszl\'o Sz\'ekely and Stephan Wagner},
title = {Paths vs. stars in the local profile of trees},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {1},
doi = {10.37236/5943},
zbl = {1355.05082},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5943/}
}
TY - JOUR
AU - Éva Czabarka
AU - László Székely
AU - Stephan Wagner
TI - Paths vs. stars in the local profile of trees
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/5943/
DO - 10.37236/5943
ID - 10_37236_5943
ER -
%0 Journal Article
%A Éva Czabarka
%A László Székely
%A Stephan Wagner
%T Paths vs. stars in the local profile of trees
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/5943/
%R 10.37236/5943
%F 10_37236_5943
Éva Czabarka; László Székely; Stephan Wagner. Paths vs. stars in the local profile of trees. The electronic journal of combinatorics, Tome 24 (2017) no. 1. doi: 10.37236/5943
