Monday, June 21, 3pm ET (8pm BST, 7am Tue NZST)
Sebastian Wiederrecht, LIRMM
Even Circuits in Oriented Matroids
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.