Online event: Open problems session

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.

Date: Monday, December 14 (1:30 – 4:00pm ET)
 
Schedule:
Session 1 (matroids): 1:30 – 2:30pm ET
Session 2 (graphs): 3:00 – 4:00pm ET
Beer time: After that 🙂
 
Format: We’ll have a short presentation about each problem followed by some time for discussion. There will likely be time at the end for further impromptu problems as well. We will also link to a Discord server as a suggested way of discussing problems via text.
 
Session 1 presenters:
Nathan Bowler – slides
Daniel Bernstein – slides
Dillon Mayhew – slides
Peter Nelson – slides
Relinde Jurrius – slides
Jim Geelen – slides
 
Session 2 presenters:
Maria Chudnovsky – slides
Youngho Yoo – slides
Chun-Hung Liu – slides
Ben Moore – slides
Johannes Carmesin – slides
Rose McCarty – slides

 

Online talk: Sergey Norin

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.

Online talk: Johannes Carmesin

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.