Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count. (English) Zbl 1399.05029
Authors’ 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.
Reviewer: Ágota H. Temesvári (Budapest)
MSC:
| 05B40 | Combinatorial aspects of packing and covering |
| 05C12 | Distance in graphs |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 90C05 | Linear programming |
Keywords:
superlinear subset partition; dimension reduction; strong adjacency; endpoint count; diameter; polytopeReferences:
| [1] | I. Adler: Abstract Polytopes, PhD thesis, Stanford University, Stanford, CA, 1971. |
| [2] | I. Adler: Mathematical Programming Study I: Pivoting and Extensions, chapter Lower bounds for maximum diameters of polytopes, North-Holland, 1974. |
| [3] | I. Adler, G. Dantzig and K. Murty: Mathematical Programming Study: Pivoting and Extension, chapter Existence of A-avoiding paths in abstract polytopes, NorthHolland, 1974. · Zbl 0352.90037 |
| [4] | I. Adler and G. B. Dantzig: Mathematical Programming Study: Pivoting and Extension, chapter Maximum diameter of abstract polytopes, North-Holland, 1974. |
| [5] | I. Adler and R. Saigal: Long monotone paths in abstract pol · Zbl 0457.90047 · doi:10.1287/moor.1.1.89 |
| [6] | N. Alon and J. H. Spencer: The Probabilistic Method, 3rd edition, John Wiley and Sons, Inc., Hoboken, NJ, 2008. · Zbl 1148.05001 |
| [7] | D. Barnette: Wv paths on 3-poly · Zbl 0177.26804 · doi:10.1016/S0021-9800(69)80007-4 |
| [8] | D. Barnette: An upper bound for the diameter of a · Zbl 0294.52007 · doi:10.1016/0012-365X(74)90016-8 |
| [9] | V. Chvátal: The tail of the hypergeometric dist · Zbl 0396.60016 · doi:10.1016/0012-365X(79)90084-0 |
| [10] | F. Eisenbrand, N. Hähnle, A. Razborov and T. Rothvoss: Diameter of polyhedra: Limits of abstr · Zbl 1226.52004 · doi:10.1287/moor.1100.0470 |
| [11] | F. Eisenbrand: Comments on: Recent progress on the combinatorial diameter of polytopes and s · Zbl 1311.52011 · doi:10.1007/s11750-013-0292-x |
| [12] | W. Feller: Probability Theory and its Applications, Volume One. John Wiley and Sons, Inc., New York, NY, 1950. · Zbl 0039.13201 |
| [13] | M. Goresky and R. MacPherson: Intersection h · Zbl 0448.55004 · doi:10.1016/0040-9383(80)90003-8 |
| [14] | B. Grünbaum: Convex Polytopes, Number 221 in Graduate Texts in Mathematics, Springer-Verlag, New York, NY, 2nd edition, 2003. |
| [15] | N. Hähnle: Constructing subset partition graphs with strong adjacency and endpoint count properties, Available at arXiv:1203.1525v1, 2012. |
| [16] | W. Hoeffding: Probability Inequalities for Sums of Bounded Random Variables, · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830 |
| [17] | G. Kalai: Upper bounds for the diameter and height of graphs of convex polyhedra · Zbl 0764.52003 · doi:10.1007/BF02293053 |
| [18] | G. Kalai and D. J. Kleitman: A quasi-polynomial bound for the diameter of graphs of polyhedra · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9 |
| [19] | E. D. Kim: Polyhedral graph abstractions and an approach to the Linear Hirsch conjecture · Zbl 1290.05067 · doi:10.1007/s10107-012-0611-2 |
| [20] | E. D. Kim and F. Santos: An update on the Hirsch conjecture, Jahr · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8 |
| [21] | V. Klee and P. Kleinschmidt: The d-step conjecture and its rel · Zbl 0632.52007 · doi:10.1287/moor.12.4.718 |
| [22] | V. Klee and D. W. Walkup: The d-step conjecture for polyhedra of dime · Zbl 0163.16801 · doi:10.1007/BF02395040 |
| [23] | D. G. Larman: Paths on polytopes · Zbl 0199.59301 · doi:10.1112/plms/s3-20.1.161 |
| [24] | J. A. Lawrence: Abstract polytopes and the Hirsch co · Zbl 0386.52006 · doi:10.1007/BF01609004 |
| [25] | B. Matschke, F. Santos and C. Weibel: The width of 5-dimensional prismatoids, Proceedings of the London Mathematical Society (2015): pdu064. · Zbl 1330.52015 |
| [26] | K. G. Murty: The graph of an abstract · Zbl 0271.52007 · doi:10.1007/BF01584675 |
| [27] | I. Novik and E. Swartz: Face numbers of pseudomanifolds with isolated singularities, · Zbl 1255.13014 · doi:10.7146/math.scand.a-15204 |
| [28] | F. Santos: A counterexample to the Hirsc · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7 |
| [29] | F. Santos: Recent progress on the combinatorial diameter of polytopes and s · Zbl 1280.52011 · doi:10.1007/s11750-013-0295-7 |
| [30] | M. Skala: Hypergeometric tail inequalities: ending the insanity, available at arXiv:1311.5939v1, 2013. |
| [31] | M. J. Todd: An improved Kalai-Kleitman bound for the diameter of a polyhedron, available at arXiv:1402.3579v2, 2014. · Zbl 1316.52021 |
| [32] | G. M. Ziegler: Lectures on Polytopes, Number 152 in Graduate Texts in Mathematics, Springer-Verlag, New York, NY, 1994. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
