기초과학연구원 이산수학그룹
On December 9, 2020, Karl Heuer from Technische Universität Berlin gave an online talk on the problem of detecting even directed circuits in a regular oriented matroid and related classes of oriented matroids at the Virtual Discrete Math Colloquium. The title of his talk was “Even Circuits in Oriented Matroids“.
In this talk I will state a generalisation of the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. Motivated by this problem, I will 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 I will present and discuss our two results regarding these notions:
First we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.
Second and with the main focus for this talk, we shall characterise 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. The second result makes use of a new concept of minors for oriented matroids, which generalises butterfly minors for digraphs to oriented matroids.
The part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory.
This talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht.
[1] K. Heuer, R. Steiner and S. Wiederrecht, Even Circuits in Oriented Matroids, arxiv:2010.08988