Department of
Applied
Mathematics

Paths vs. stars in the local profile of trees

Stephan Wagner

Abstract

For a given subtree size k, the local profile of a tree describes the distribution of the subtrees of size k in isomorphism classes. In this talk, we focus on paths and stars and provide an affirmative answer to a recent question by Bubeck and Linial. 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)->0 for a sequence of trees T_1,T_2,... whose size tends to infinity, then p^(k)_2(T_n)->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.