Mathematics – Combinatorics
Scientific paper
2012-03-07
Mathematics
Combinatorics
Scientific paper
Kim defined a very general combinatorial abstraction of the diameter of polytopes called subset partition graphs to study how certain combinatorial properties of such graphs may be achieved in lower bound constructions. Using Lov\'asz' 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 our method to construct abstract spindles, an analogy to the spindles used by Santos to disprove the Hirsch conjecture, of exponential length which satisfy the adjacency and end-point count properties.
No associations
LandOfFree
Constructing subset partition graphs with strong adjacency and end-point count properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constructing subset partition graphs with strong adjacency and end-point count properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing subset partition graphs with strong adjacency and end-point count properties will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-394791