Even circuits in oriented matroids

by Dr Karl Heuer (Technical University of Denmark)

Tuesday 17 Oct 2023, 17:00 → 18:00 Europe/Berlin

H4 (Geom)

Abstract:
This talk is motivated by a fundamental and simple looking decision problem in Graph Theory, known as the Even Directed Cycle Problem: Decide whether a given directed graph contains a directed cycle of even length. The answer to this problem turned out to be complicated, but a quick algorithm was found to answer this decision problem. Directed graphs that admit a quite special set of edges (a so-called “odd feedback arc set”) played an important role in the corresponding work.

In this talk I will present a new problem, which is dual to the Even Directed Cycle Problem, and lift it even further into the context of oriented matroids. Furthermore, I shall speak about our result that characterises directed graphs that admit the dual of an odd feedback arc set, which is called an “odd dijoin”. The characterisation will be in terms of forbidden substructures with respect to a new containment relation for directed graphs (and oriented matroids). I shall also point out in which sense our newly suggested relation generalises the so-called butterfly-minor relation, which is quite common for directed graphs.

This talk is based on joint work with Raphael Steiner and Sebastian Wiederrecht (https://doi.org/10.5070/C62156875).