The open problems session is next week! There are two sessions: Session 1 loosely focused on matroids and Session 2 loosely focused on graphs. Anyone interested in the topics is welcome to join; no registration is required. The sessions will not be recorded, but we will update this page linking to the slide(s) of each presenter.

Monday, December 7, 3pm ET (8pm GMT, 9am Tue NZDT)
Sergey Norin, McGill University
Densities of minor-closed graph classes

Youtube

Abstract:

The density of a sparse graph class is the supremum of the ratio $|E(G)|/|V(G)|$ taken over all non-null graphs $G$ in the class. The densities of graph classes determined by forbidding a single minor have been extensively studied, in part due to connections to the Hadwiger’s conjecture.

We will survey recent results on densities of minor-closed graph classes, including a proof of the conjecture of Eppstein that the densities of minor-closed graph classes are rational, joint with Rohan Kapadia, and joint work with Kevin Hendrey, Bruce Reed, Andrew Thomason and David Wood on densities of classes which forbid a single sparse minor.

Monday, November 30, 3pm ET (8pm GMT, 9am Tue NZDT)
Johannes Carmesin, University of Birmingham
Matroids and embedding graphs in surfaces

Youtube

Abstract:

Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, this problem would be NP-hard. Instead of minimum genus, here we use local planarity — and provide a polynomial algorithm.

Our embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.