Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count

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.

24 pages, 6 figures, to appear in Combinatorica

References in corpus (3)

• Hypergeometric tail inequalities: ending the insanity
• Constructing subset partition graphs with strong adjacency and end-point count properties
• An improved Kalai-Kleitman bound for the diameter of a polyhedron

Cited by in corpus (2)

• An improved upper bound on the diameters of subset partition graphs
• Tail diameter upper bounds for polytopes and polyhedra