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
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.

Online talk: Sarah Allred

Monday, November 23, 3pm ET (8pm GMT, 9am Tue NZDT)
Sarah Allred, LSU
Unavoidable Induced Subgraphs of Large 2-connected Graphs
It is well known that, for every positive integer $r$, every sufficiently large connected graph contains an induced subgraph isomorphic to one of the following: a large complete graph, a large star, and a long path.  We prove an analogous result for 2-connected graphs.  In particular, we show that every sufficiently large 2-connected graph contains an induced subgraph isomorphic to one of the following: a complete graph, a subdivision of $K_{2,r}$ with possibly an edge joining the two vertices of degree $r$, and a graph that has a well-described ladder structure.
This is joint work with Guoli Ding and Bogdan Oporowski. 

Online talk: Jakob Kneip

Monday, November 16, 3pm ET (8pm GMT, 9am Tue NZDT)
Jakob Kneip, Universität Hamburg
Tangles are decided by weighted vertex sets
Slides (view pdf)

Tangles are a way to capture clusters or highly cohesive regions in graphs: a tangle in a graph declares for each low-order separation one of the two sides of that separation as ‘big’, and does so in such a way that no three ‘small’ sides together cover the graph. Most types of clusters in graphs — for instance clique- or grid-minors — give rise to such a tangle by declaring as ‘big’ for each separation the side which contains the majority of the vertices of that cluster.

An open question in the theory of tangles is whether a converse to this holds: given a tangle in a graph, can we find a set of vertices such that the ‘big’ side of each separation is precisely the side which contains the majority of the set’s vertices? A positive answer to this would validate the intuition that the sides declared as ‘big’ by a tangle are in fact big in some sense.

In joint work with Christian Elbracht and Maximilian Teegen we show that a fractional version of this is true: given a tangle we construct a weight function on the vertices such the ‘big’ side of each separation is exactly the side with higher total weight. We also show that our result extends to tangles of hypergraphs as well as to edge tangles, which are based on cuts rather than vertex separations. Curiously though one cannot achieve both extensions simultaneously: there are edge tangles of hypergraphs that are not defined by such a weight function on the vertices.

Open Problems Session- Dec 14

For the last week of the “Graphs and Matroids” seminar this year, on December 14th we will hold an open problems session from 1:30 – 4:00pm ET with beer time afterwards (BYOB 🙂 ). The idea is to better mimic an in-person conference with time for problems, discussions, and informal chats. For each problem, we’ll have a <5 minute slide presentation, plus a little time for discussion afterwards. There will be two sessions of about an hour each with a break in-between. 

If you want to present a problem, please email [rose.mccarty @]. No details are needed yet, but if you can’t make both of the sessions please say which one you’ll be attending (earlier or later).

And if you have any suggestions for best practices/software/etc. for an online event like this, please also email [rose.mccarty @]. We have some ideas but are still learning about this new format as we go.

Further details (ie how to connect to the event) will follow in another blog post closer to December 14.

-Jim, Peter, and Rose

Edit: Please email by the end of the day on December 7th (Anywhere on Earth).