Springe direkt zu Inhalt

Lecture by Kolja Knauer (Aix-Marseille Université): Tope graphs of (Complexes of) Oriented Matroids

Apr 29, 2019 | 02:15 PM

Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain so-called antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory.

Based on joint work with H.-J; Bandelt, V. Chepoi, and T. Marc.

Time & Location

Apr 29, 2019 | 02:15 PM

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room MA 041 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)