Jesse Campion Loth

Enumerating graph embeddings

It is a classical problem to find the smallest genus surface a graph may be embedded on. However any graph has many different embeddings on different surfaces. A natural question is then, given a graph G and a surface \Sigma, how many embeddings does G have on \Sigma? We will give a basic introduction to this question, and show how it is perhaps too difficult to solve in general. We then focus on recent results which show how combinatorial random processes can estimate the 'average genus' of a graph across all of its embeddings. We then show how the representation theory of the symmetric group can be used to obtain asymptotic results.