On the Holt-Klee property for oriented matroid programming

DOI10.1016/J.EJC.2021.103460MaRDI QIDQ2065995zbMATH OpenOpenAlexFDO

Authors Walter Morris

Publication date 13 January 2022

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

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

zbMATH Keywords

Holt-Klee theoremoriented matroid programs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Computational aspects related to convexity (52B55) Oriented matroids in discrete geometry (52C40) Linear programming (90C05)

Abstract: The Holt-Klee theorem says that the graph of a $d$-polytope, with edges oriented by a linear function on $P$ that is not constant on any edge, admits $d$ independent monotone paths from the source to the sink. We prove that the digraphs obtained from oriented matroid programs of rank $d+1$ on $n+2$ elements, which include those from $d$-polytopes with $n$ facets, admit $d$ independent monotone paths from source to sink if $dle4$. This was previously only known to hold for $dle3$ and $nle6$.

Recommendations

• The Holt-Klee condition for oriented matroids
• On the length of monotone paths in polyhedra
• Computing monotone disjoint paths on polytopes
• On combinatorial properties of linear program digraphs
• LP-orientations of cubes and crosspolytopes

Cites work

• A combinatorial abstraction of linear programming
• A Mihalisin-Klee theorem for fans
• A proof of the strict monotone 5-step conjecture
• Complementarity in Oriented Matroids
• Convex and linear orientations of polytopal graphs
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Edge-graph diameter bounds for convex polytopes with few facets
• Enumeration of PLCP-orientations of the 4-cube
• Graph theorems for manifolds
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• More bounds on the diameters of convex polytopes
• On the graph structure of convex polyhedra in n-space
• Oriented Matroids
• Oriented matroids
• Signable posets and partitionable simplicial complexes
• The Holt-Klee condition for oriented matroids
• Triangulations of oriented matroids
• Unique sink orientations of grids

Cited in

(6)

• Computing monotone disjoint paths on polytopes
• The Holt-Klee condition for oriented matroids
• Families of polytopal digraphs that do not satisfy the shelling property
• A Mihalisin-Klee theorem for fans
• On combinatorial properties of linear program digraphs
• LP-orientations of cubes and crosspolytopes

This page was built for publication: On the Holt-Klee property for oriented matroid programming

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