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.

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.

Monday, May 31, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Slilaty, Wright State University
Orientations of golden-mean matroids

Abstract:

Tutte proved that a binary matroid is representable over some field of characteristic other than 2 if and only if the matroid is regular. His result inspired the discovery of analogs for $GF(3)$-representable matroids by Whittle, $GF(4)$-representable matroids by Vertigan as well as Pendavingh and Van Zwam, and $GF(5)$-representable matroids by Pendavingh and Van Zwam.

Bland and Las Vergnas proved that a binary matroid’s orientations correspond to its regular representations. (Minty’s result on digraphoids is closely related.) Lee and Scobee proved that a $GF(3)$-representable matroid’s orientations correspond to its dyadic representations. In this talk we will explore orientations of $GF(4)$-representable matroids. A natural partial field to use is the golden-mean partial field; however, not every orientation of a $GF(4)$-representable matroid comes from a golden-mean representation. For example, $U_{3,6}$ has 372 orientations but only 12 of them come from golden-mean representations. We will give a combinatorial characterization of those orientations of $GF(4)$-representable matroids which do come from golden-mean representations and show that these orientations correspond one-to-one to the golden-mean representations.

Joint work with Jakayla Robbins.