Inducibility and universality for trees

Timothy Chan, Daniel Král’, Bojan Mohar, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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

Original languageEnglish
Article number2
Number of pages31
JournalCombinatorial Theory
Volume2
Issue number3
DOIs
Publication statusPublished - 2022

Keywords

  • graph density
  • inducibility
  • Trees

Cite this