Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
arXiv:1409.7133
Abstract
We construct a sequence of subset partition graphs satisfying the dimension reduction, adjacency, strong adjacency, and endpoint count properties whose diameter has a superlinear asymptotic lower bound. These abstractions of polytope graphs give further evidence against the Linear Hirsch Conjecture.
arXiv comment24 pages, 6 figures, to appear in Combinatorica
References in corpus (6)
- A counterexample to the Hirsch conjecture
- Hypergeometric tail inequalities: ending the insanity
- The width of 5-dimensional prismatoids
- Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Constructing subset partition graphs with strong adjacency and end-point count properties
- An improved Kalai-Kleitman bound for the diameter of a polyhedron