Article contents
Subgraph densities in a surface
Published online by Cambridge University Press: 11 January 2022
Abstract
Given a fixed graph H that embeds in a surface $\Sigma$ , what is the maximum number of copies of H in an n-vertex graph G that embeds in $\Sigma$ ? We show that the answer is $\Theta(n^{f(H)})$ , where f(H) is a graph invariant called the ‘flap-number’ of H, which is independent of $\Sigma$ . This simultaneously answers two open problems posed by Eppstein ((1993) J. Graph Theory17(3) 409–416.). The same proof also answers the question for minor-closed classes. That is, if H is a $K_{3,t}$ minor-free graph, then the maximum number of copies of H in an n-vertex $K_{3,t}$ minor-free graph G is $\Theta(n^{f'(H)})$ , where f′(H) is a graph invariant closely related to the flap-number of H. Finally, when H is a complete graph we give more precise answers.
MSC classification
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2022. Published by Cambridge University Press
Footnotes
All three authors are supported by the Australian Research Council. G. Joret is supported by an ARC grant from the Wallonia-Brussels Federation of Belgium and a CDR grant from the National Fund for Scientific Research (FNRS).
References
- 5
- Cited by