Constructing subset partition graphs with strong adjacency and end-point count properties

Abstract

Kim defined a very general combinatorial abstraction of the diameter of polytopes called subset partition graphs to study howcertain combinatorial properties of such graphsmay be achieved in lower bound constructions. Using Lovász’ Local Lemma, we give a general randomized construction for subset partition graphs satisfying strong adjacency and end-point count properties. This can be used as a building block to conceptually simplify the constructions given in [Kim11]. We also use ourmethod to construct abstract spindles, an analogy to the spindles used by Santos [San10] to disprove the Hirsch conjecture, of exponential length which satisfy the adjacency and end-point count properties.

Topics

    1 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)