Monash

We study the following question at the intersection of extremal and structural graph theory. Given a fixed graph $H$ that embeds in a fixed surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Exact answers to this question are known for specific graphs $H$ when $\Sigma$ is the sphere. We aim for more general, albeit less precise, results. We show that the answer to the above question is $\Theta(nf(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. This is joint work with Tony Huynh and Gwenaël Joret [https://arxiv.org/abs/2003.13777]