Some variations on connected layer families

Edward Kim
Technische Universiteit te Delft

Combinatorial abstractions of the graphs of polyhedra were
considered by Adler, Dantzig, and Murty (abstract polytopes) and Kalai
(ultraconnected set systems). More recently Eisenbrand, H\"ahnle,
Razborov, and Rothvo\ss{} 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 and showing how they fit into
a more general framework, which naturally leads to some variants of
these earlier abstractions. We then focus on special subclasses in the
new framework. In particular, we define a specific kind of combinatorial
prismatoid, inspired by the use of prismatoid widths in Santos'
counterexample to the Hirsch Conjecture. We define a notion of width for
these combinatorial prismatoids and prove that it is superlinear.

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?