On tope graphs of complexes of oriented matroids
From MaRDI portal
Abstract: We give two graph theoretical characterizations of tope graphs of (complexes of) oriented matroids. The first is in terms of excluded partial cube minors, the second is that all antipodal subgraphs are gated. A direct consequence is a third characterization in terms of zone graphs of tope graphs. Further 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. Furthermore, we obtain polynomial time recognition algorithms for tope graphs of the above and a finite list of excluded partial cube minors for the bounded rank case. In particular, this answers a relatively long-standing open question in oriented matroids. Another consequence is that all finite Pasch graphs are tope graphs of complexes of oriented matroids, which confirms a conjecture of Chepoi and the two authors.
Recommendations
Cites work
- A characterization of oriented matroids in terms of topes
- A characterization of planar partial cubes
- A combinatorial perspective on the non-Radon partitions
- A correction of a characterization of planar partial cubes
- Antipodal graphs and oriented matroids
- Axioms for maximal vectors of an oriented matroid: A combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes
- Combinatorial face enumeration in arrangements and oriented matroids
- COMs: complexes of oriented matroids
- Convex excess in partial cubes
- Convexity in partial cubes: the hull number
- Cross-cloning and antipodal graphs
- Distance-preserving subgraphs of hypercubes
- Finitary affine oriented matroids
- Gated sets in metric spaces
- Graphs and cubes
- Graphs with intrinsic s3 convexities
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
- Hyperplane arrangements with a lattice of regions
- Isometric Diamond Subgraphs
- Isometric embedding in products of complete graphs
- Isometric subgraphs of Hamming graphs and d-convexity
- Lopsided sets and orthant-intersection by convex sets
- Media theory. Interdisciplinary applied mathematics.
- On bipartite graphs whose interval space is a closed join space
- On the Addressing Problem for Loop Switching
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Oriented Matroids
- Recognizing partial cubes in quadratic time
- Separation of two convex sets in convexity structures
- The axiomatization of affine oriented matroids reassessed
- There are no finite partial cubes of girth more than 6 and minimum degree at least 3
- Topes of oriented matroids and related structures
Cited in
(24)- Spatial graphs and oriented matroids: The trefoil
- Generation of oriented matroids --- a graph theoretical approach
- COMs: complexes of oriented matroids
- A characterization of oriented matroids in terms of topes
- On antipodal and diametrical partial cubes
- On some properties of antipodal partial cubes
- Topes of oriented matroids and related structures
- A characterization of cocircuit graphs of uniform oriented matroids
- A graph-theoretical axiomatization of oriented matroids
- Ample completions of oriented matroids and complexes of uniform oriented matroids
- Transit sets of two-point crossover
- On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3
- Corners and simpliciality in oriented matroids and partial cubes
- Compression schemes for concept classes induced by three types of discrete undirected graphical models
- First-order logic axiomatization of metric graph theory
- On \(k\)-neighborly reorientations of oriented matroids
- Labeled sample compression schemes for complexes of oriented matroids
- Finitary affine oriented matroids
- A homotopy theorem on oriented matroids
- Antipodal graphs and oriented matroids
- The signed Varchenko determinant for complexes of oriented matroids
- Geometry of convex geometries
- Inseparability graphs of oriented matroids
- Two-dimensional partial cubes
This page was built for publication: On tope graphs of complexes of oriented matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291453)
