Subgraph densities in a surface
Tony Huynh, Gwenaël Joret, David R. Wood
Abstract
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 Theory 17 (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.