The Holt-Klee condition for oriented matroids

DOI10.1016/J.EJC.2008.12.012MaRDI QIDQ1041605zbMATH OpenOpenAlexFDO

Authors Komei Fukuda, Sonoko Moriyama, Yoshio Okamoto

Publication date 3 December 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612073

zbMATH Keywords

Holt-Kleeoriented matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: Holt and Klee have recently shown that every (generic) LP orientation of the graph of a $d$-polytope satisfies a directed version of the $d$-connectivity property, i.e. there are $d$ internally disjoint directed paths from a unique source to a unique sink. We introduce two new classes HK and HK* of oriented matroids (OMs) by enforcing this property and its dual interpretation in terms of line shellings, respectively. Both classes contain all representable OMs by the Holt-Klee theorem. While we give a construction of an infinite family of non-HK* OMs, it is not clear whether there exists any non-HK OM. This leads to a fundamental question as to whether the Holt-Klee theorem can be proven combinatorially by using the OM axioms only. Finally, we give the complete classification of OM(4, 8), the OMs of rank 4 on 8-element ground set with respect to the HK, HK*, Euclidean and Shannon properties. Our classification shows that there exists no non-HK OM in this class.

Review text

It has recently been shown by \textit{F. Holt} and \textit{V. Klee} [Contemp. Math. 223, 201--216 (1999; Zbl 0916.90206)] that every (generic) LP orientation of the graph of a \(d\)-polytope satisfies a directed version of the \(d\)-connectivity property, i.e., there are \(d\) internally disjoint directed paths from a unique source to a unique sink. By enforcing this property and its dual interpretation in terms of line shellings, two new classes of orientated matroids \(HK\) and \(HK^*\) are introduced in the paper under review. Both classes contain all representable oriented matroids by the Holt-Klee theorem. The authors provide a construction of an infinite family of non-\(HK^*\) oriented matroids, but it is not clear whether there exists any non-\(HK\) oriented matroid. The authors give a complete classification of the oriented matroids of rank 4 on 8-element ground set with respect to the \(HK\), \(HK^*\), Euclidean and Shannon properties. The classification shows that there exists no non-\(HK\) oriented matroid in this class.

Recommendations

• On the Holt-Klee property for oriented matroid programming
• LP-orientations of cubes and crosspolytopes
• scientific article; zbMATH DE number 3869347
• scientific article; zbMATH DE number 54123
• Reconstruction of the orientation class of an oriented matroid

Cites work

• A lower bound on the number of cells in arrangements of hyperplanes
• A non-geometric shelling of a 3-polytope
• Convex and linear orientations of polytopal graphs
• scientific article; zbMATH DE number 4053635 (Why is no real title available?)
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• scientific article; zbMATH DE number 2209726 (Why is no real title available?)
• On the graph structure of convex polyhedra in n-space
• Oriented matroids
• Oriented Matroids
• Shellable Decompositions of Cells and Spheres.
• Shelling polyhedral 3-balls and 4-polytopes
• Simplicial cells in arrangements and mutations of oriented matroids
• Simplicial cells in arrangements of hyperplanes

Cited in

(5)

• Complete enumeration of small realizable oriented matroids
• On the Holt-Klee property for oriented matroid programming
• A Mihalisin-Klee theorem for fans
• scientific article; zbMATH DE number 4191661 (Why is no real title available?)
• LP-orientations of cubes and crosspolytopes

This page was built for publication: The Holt-Klee condition for oriented matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1041605)