Online Talk: Sebastian Wiederrecht

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.