Combinatorial Abstractions of Polyhedral Graphs and the Linear Hirsch Conjecture

Edward D. Kim, TU Delft

Combinatorial abstractions of the graphs of polyhedra are receiving renewed interest as an approach to the Linear Hirsch and Polynomial Hirsch Conjectures (see the Polymath3 project) since Santos disproved the Hirsch Conjecture. Previous abstractions of polyhedral graphs were considered by Adler, Dantzig, and Murty (abstract polytopes) and Kalai (ultraconnected set systems). More recently Eisenbrand, Hähnle, Razborov, and Rothvoß introduced a slightly more general class of objects (called connected layer families) and proved a superlinear lower bound on their diameters. In this talk, we give a survey of these abstractions, giving complete definitions.
Then we show how they fit into a more general framework, which leads to some variants of these earlier abstractions. This framework is a new combinatorial abstraction for the graphs of polyhedra, providing a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete approach for disproving the Linear Hirsch Conjecture.