Inducibility and universality for trees

Abstract

We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive ${\epsilon }_1$ and ${\epsilon }_2$ such that every tree that is neither a path nor a star has inducibility at most $1-{\epsilon }_1$, where the inducibility of a tree $T$ is defined as the maximum limit density of $T$, and that there are infinitely many trees with inducibility at least ${\epsilon }_2$. Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.

31 pages, 8 figures