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

banner complexcombinatorial segmentdiameterflag complexnormal complexsimplicial complex

Mathematics Subject Classification ID

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

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.

Review text

In this article authors give constructions of combinatorial segments (as defined by Adiprasito and Benedetti, these are certain types of paths in dual graphs of pure complexes). Their properties like their maximum lengths, their behavior with respect to the classical operations on the simplicial complexes etc. have been investigated by introducing the notion of monotonic conservative paths. Authors construct monotone conservative paths in banner complexes and give upper bounds for the lengths of these paths. Authors also construct exponentially long monotone conservative paths using the notion of join and one point suspension and give lower bounds for the lengths of these paths. Limitations of combinatorial segments have also been studied using exponentially long combinatorial segments in the normal complexes. Some results of Adiprasito and Benedetti have been re-proved here. The paper is long, technical and difficult to read.

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

• 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
• scientific article; zbMATH DE number 3614497 (Why is no real title available?)
• Intersection homology theory
• Paths on Polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The Hirsch conjecture holds for normal flag complexes
• 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

(7)

• On the circuit diameter conjecture
• Distance between vertices of lattice polytopes
• 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
• The Hirsch conjecture holds for normal flag complexes
• Asymptotic bounds on the combinatorial diameter of random 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)