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

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

2012-03-07

arxiv.org/abs/1203.1525v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394791