# On tope graphs of (Complexes of) Oriented Matroids

## Kolja Knauer, University of Barcelonad

## Date and time: 6pm, Tuesday, December 17, 2019

## Place: Courant Institute, WWH1314

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.