Inducibility and universality for trees

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHAN Timothy, F. N. KRÁĽ Daniel MOHAR Bojan WOOD David R.

Year of publication 2022
Type Article in Periodical
Magazine / Source Combinatorial Theory
MU Faculty or unit

Faculty of Informatics

Citation
Web https://doi.org/10.5070/C62359150
Doi http://dx.doi.org/10.5070/C62359150
Keywords trees; inducibility; graph density
Description We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive e1 and e2 such that every tree that is neither a path nor a star has inducibility at most 1-e1, 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 e2. Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.