Subgraph densities in a surface
share
Given a fixed graph H that embeds in a surface Σ, what is the maximum number of copies of H in an n-vertex graph G that embeds in Σ? We show that the answer is Θ(n^f(H)), where f(H) is a graph invariant called the `flap-number' of H, which is independent of Σ. This simultaneously answers two open problems posed by Eppstein (1993). When H is a complete graph we give more precise answers.
READ FULL TEXT