On the Holt-Klee property for oriented matroid programming

DOI10.1016/J.EJC.2021.103460zbMATH Open1480.05063arXiv2109.15116OpenAlexW3213521534MaRDI QIDQ2065995FDOQ2065995

Walter Morris

Publication date: 13 January 2022

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

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$.

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

zbMATH Keywords

Holt-Klee theoremoriented matroid programs

Mathematics Subject Classification ID

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

Cites Work

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

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)