The Holt-Klee condition for oriented matroids
| dc.creator | Fukuda, Komei | |
| dc.creator | Moriyama, Sonoko | |
| dc.creator | Okamoto, Yoshio | |
| dc.date | 2006-12-03 | |
| dc.date | 2007-05-30 | |
| dc.date.accessioned | 2026-07-07T08:08:27Z | |
| dc.date.available | 2026-07-07T08:08:27Z | |
| dc.description | 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. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/math/0612073 | |
| dc.identifier | http://arxiv.org/abs/math/0612073 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131271 | |
| dc.subject | Combinatorics | |
| dc.subject | 52B40; 52C40; 52B22; 90C05 | |
| dc.title | The Holt-Klee condition for oriented matroids | |
| dc.type | text |