Crossing numbers of dense graphs on surfaces

Arnaud de Mesmay (LIGM)

Summary

This talk will start with an introduction to crossing numbers of dense graphs, and in particular complete graphs, focusing on the geometric aspects. Then we will present our main results: new upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if G is a dense enough graph with m edges and S is a surface of genus g, then any drawing of G on S incurs at least $\Omega(m^2 \log^2 g/g)$ crossings. The poly-logarithmic factor in this lower bound is new even in the case of complete graphs and disproves a conjecture of Shahrokhi, Székely and Vrt'o from 1996. Then we prove a geometric converse to this lower bound: we provide an explicit family of hyperbolic surfaces such that for any graph G, sampling the vertices uniformly at random on this surface and connecting them with shortest paths yields $O(m^2 \log^2g/g)$ crossings in expectation. Both results rely on hyperbolic geometry, to which we will provide a beginner-friendly introduction, and we will in particular do our best to explain why and how this ingredient occurs naturally in our proofs.

Based on joint work with Alfredo Hubard and Hugo Parlier