Online Talk: Carla Groenland

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

Password: email shaylaredlin ~at~ gmail ~.~ com (The password is the same format as usual.)
 
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.

Online Talk: Sebastian Wiederrecht

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.

Online Talk: Youngho Yoo

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.

Online Talk: Abhinav Shantanam

Monday, June 7, 3pm ET (8pm BST, 7am Tue NZST)
Abhinav Shantanam, Simon Fraser University
Pancyclicity in $4$-connected planar graphs

 
Abstract:
A graph on $n$ vertices is said to be pancyclic if, for each $k \in \{3,…,n\}$, it contains a cycle of length $k$. Following Bondy’s meta-conjecture that almost any nontrivial condition on a graph which implies Hamiltonicity also implies pancyclicity, Malkevitch conjectured that a $4$-regular, $4$-connected planar graph containing a $4$-cycle is pancyclic. We show that, for any edge $e$ in a $4$-connected planar graph $G$, there exist $\lambda(n-2)$ cycles of pairwise distinct lengths containing $e$, where $5/12 \leq \lambda \leq 2/3$. Joint work with Bojan Mohar.