Subgraph densities in a surface

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). When $H$ is a complete graph we give more precise answers.

v4: referee's comments implemented. v3: proof of the main theorem fully rewritten, fixes a serious error in the previous version found by Kevin Hendrey

References in corpus (4)

• Irreducible triangulations of low genus surfaces
• Generating irreducible triangulations of surfaces
• Tree densities in sparse graph classes
• Homomorphism counts in robustly sparse graphs

Cited by in corpus (5)

• Tree densities in sparse graph classes
• Maximizing five-cycles in $K_r$-free graphs
• Homomorphism counts in robustly sparse graphs
• Counting cycles in planar triangulations
• Planar graphs with the maximum number of induced 6-cycles