Online talk: Tony Huynh

Mon, August 31, 3pm ET (8pm BST, 7am Tue NZST)
Tony Huynh, Monash University
Subgraph densities in a surface

We consider the following problem at the intersection of extremal and structural graph theory. Given a fixed graph $H$ and surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Here a copy means a subgraph isomorphic to $H$. Exact answers are known for some $H$ when $\Sigma$ is the sphere. Our main result answers the question for all $H$ and $\Sigma$ (up to a constant factor). 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 the surface $\Sigma$.

This is joint work with Gwenaƫl Joret and David Wood.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.