Monday, July 5, 3pm ET (8pm BST, 7am Tue NZST)
Shayla Redlin, University of Waterloo
Extensions of cliques

Abstract:

In this talk, we will investigate the extensions of the cycle matroid of a complete graph. I will show that the number of these extensions is surprisingly large.

This is joint work with Peter Nelson and Jorn van der Pol.

Monday, June 28, 3pm ET (8pm BST, 7am Tue NZST)
Carla Groenland, Utrecht University
Universal Graphs and Labelling Schemes

Abstract:
An induced universal graph for a graph class contains all graphs in the class as an induced subgraph. We construct induced universal graphs for all hereditary graph classes, and derive reachability labelling schemes for digraphs and comparability labelling schemes for posets from this. All these results are asymptotically optimal. This talk aims to give some intuition about these concepts and our techniques (which includes Szemerédi’s regularity lemma). We will also discuss a new venue of research: what if we strengthen induced to isometric? Several interesting questions are left open.

This is based on joint work with Marthe Bonamy, Louis Esperet, Cyril Gavoille and Alex Scott.

Monday, June 21, 3pm ET (8pm BST, 7am Tue NZST)
Sebastian Wiederrecht, LIRMM
Even Circuits in Oriented Matroids

Abstract:

This work generalises the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.
Our main result is a precise characterisation of the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen and reveals an extended class of obstructions.
This is joint work with Karl Heuer and Raphael Steiner.

Monday, June 14, 3pm ET (8pm BST, 7am Tue NZST)
Youngho Yoo, Georgia Tech
Packing A-paths of length 0 modulo a prime

Abstract:

An $A$-path is a nontrivial path with its endpoints in a vertex set $A$ that is internally disjoint from $A$. In 1961, Gallai showed that $A$-paths satisfy an approximate packing-covering duality, also known as the Erdős-Pósa property. There are many generalizations and variants of this result. In this talk, we show that the Erdős-Pósa property holds for $A$-paths of length 0 mod $p$ for every prime $p$, answering a question of Bruhn and Ulmer. The proof uses structure theorems for undirected group-labelled graphs. We also give a characterization of abelian groups $\Gamma$ and elements $\ell \in \Gamma$ for which the Erdős-Pósa property holds for $A$-paths of weight $\ell$ in undirected $\Gamma$-labelled graphs. Joint work with Robin Thomas.