Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count

2014/09/25 by Tristram C. Bogart, Bogart, Tristram C., Edward D. Kim +1
Mathematics · #05B40 #05C12 #52B05 #90C05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B40 #msc:05C12 #msc:52B05 #msc:90C05

paper · pdf · doi:10.48550/arxiv.1409.7133

24 pages, 6 figures, to appear in Combinatorica

arxiv created 2015/09/23 · arxiv updated 2015/09/25

Abstract

We construct a sequence of subset partition graphs satisfying the dimension reduction, adjacency, strong adjacency, and endpoint count properties whose diameter has a superlinear asymptotic lower bound. These abstractions of polytope graphs give further evidence against the Linear Hirsch Conjecture.

Related

• Constructing subset partition graphs with strong adjacency and end-point count properties
• An improved upper bound on the diameters of subset partition graphs
• A Formal Disproof of the Hirsch Conjecture
• A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order
• Graphs, flags and partitions