Hirsch polytopes with exponentially long combinatorial segments

DOI10.1007/S10107-016-1099-YMaRDI QIDQ1675265zbMATH OpenOpenAlexFDO

Authors Jean-Philippe Labbé, T. Manneville, Francisco Santos

Publication date 27 October 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

flag complexsimplicial complexdiameterbanner complexcombinatorial segmentnormal complex

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Combinatorial aspects of simplicial complexes (05E45)

Abstract: In their paper proving the Hirsch bound for flag normal simplicial complexes (Math. Oper.~Res.~2014) Adiprasito and Benedetti define the notion of~emph{combinatorial segment}. The study of the maximal length of these objects provides the upper bound~$O(n{2}^d)$ for the diameter of any normal pure simplicial complex of dimension~$d$ with~$n$ vertices, and the Hirsch bound $n-d$ if the complexes are, moreover, flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use this definition to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length $Omega(n{2}^d)$. This includes vertex-decomposable---therefore Hirsch---polytopes.

Recommendations

• The Hirsch conjecture holds for normal flag complexes
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Maximal nonrevisiting paths in simple polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Cites work

• scientific article; zbMATH DE number 3614497 (Why is no real title available?)
• A counterexample to the Hirsch conjecture
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• An upper bound for the diameter of a polytope
• Branched coverings
• Branched coverings, triangulations, and 3-manifolds
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• Diameter of polyhedra: limits of abstraction
• From flag complexes to banner complexes
• Intersection homology theory
• Paths on Polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• The Hirsch conjecture holds for normal flag complexes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The width of five-dimensional prismatoids
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
• Upper bounds for the diameter and height of graphs of convex polyhedra

Cited in

(6)

• On the circuit diameter conjecture
• The Hirsch conjecture holds for normal flag complexes
• An asymptotically improved upper bound on the diameter of polyhedra
• Improving bounds on the diameter of a polyhedron in high dimensions
• A Polyhedral Method for Sparse Systems with Many Positive Solutions
• Distance between vertices of lattice polytopes

This page was built for publication: Hirsch polytopes with exponentially long combinatorial segments

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