Combinatorial Theory

We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive \(\varepsilon_1\) and \(\varepsilon_2\) such that every tree that is neither a path nor a star has inducibility at most \(1-\varepsilon_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 \(\varepsilon_2\). Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.

Mathematics Subject Classifications: 05C05, 05C35

Keywords: Trees, inducibility, graph density