Polyhedral graph abstractions and an approach to the linear Hirsch conjecture. (English) Zbl 1290.05067
This paper introduces a combinatorial abstraction for the graphs of polyhedra. The author formally explain some previous abstractions and survey the upper and lower bound. This paper discuss combinatorial properties defining special cases and then a new combinatorial abstraction namely subset partition graphs. The upper and lower bounds as the diameters of the subset partition graphs satisfying a particular set of properties is discussed. Finally, a strategy is presented for disproving Linear Hirsch Conjecture.
Reviewer: G. N. Prasanth (Alappuzha)
MSC:
| 05C12 | Distance in graphs |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
References:
| [1] | Adler, I.: Abstract Polytopes. PhD thesis, Stanford University, Stanford, CA (1971) · Zbl 0457.90047 |
| [2] | Adler, I., Dantzig, G., Murty, K.: Existence of \[A\]-avoiding paths in abstract polytopes. In: Mathematical Programming Study: Pivoting and Extension, pp. 41-42. North-Holland (1974) · Zbl 0352.90037 |
| [3] | Adler, I., Dantzig, G.B.: Maximum diameter of abstract polytopes. In: Mathematical Programming Study: Pivoting and Extension, pp. 20-40. North-Holland (1974) · Zbl 0395.90051 |
| [4] | Adler, I., Saigal, R.: Long monotone paths in abstract polytopes. Math. Oper. Res. 1(1), 89-95 (1976) · Zbl 0457.90047 · doi:10.1287/moor.1.1.89 |
| [5] | Balinski, M.L.: On the graph structure of convex polyhedra in \[n\]-space. Pacific J. Math. 11, 431-434 (1961) · Zbl 0103.39602 · doi:10.2140/pjm.1961.11.431 |
| [6] | Eisenbrand, F., Hähnle, N., Razborov, A., Rothvoß, T.: Diameter of polyhedra: Limits of abstraction. Math. Oper. Res. 35(4), 786-794 (2010) · Zbl 1226.52004 · doi:10.1287/moor.1100.0470 |
| [7] | Hähnle, N.: Combinatorial abstractions for the diameter of polytopes. Universität Paderborn, Master’s thesis (2008) · Zbl 0764.52003 |
| [8] | Hähnle, N.: Constructing subset partition graphs with strong adjacency and end-point count properties (2012). arXiv:1203.1525 |
| [9] | Joswig, M., Ziegler, G.M.: Neighborly cubical polytopes. Discrete Comput. Geom. 24, 325-344 (2000) · Zbl 1066.52012 · doi:10.1007/s004540010039 |
| [10] | Kalai, G.: Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput. Geom. 8(4), 363-372 (1992) · Zbl 0764.52003 · doi:10.1007/BF02293053 |
| [11] | Kalai, G.: Polymath3: The Polynomial Hirsch Conjecture (Part 6), April (2011). Online blog: http://gilkalai.wordpress.com/2011/04/13/polymath3-phc6-the-polynomial-hirsch-conjecture-a-topological-approach/ · Zbl 0764.52003 |
| [12] | Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. 26, 315-316 (1992) · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9 |
| [13] | Kim, E.D., Santos, F.: An update on the Hirsch conjecture. Jahresber. Dtsch. Math. Ver. 112(2), 73-98 (2010) · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8 |
| [14] | Klee, V.: Paths on polyhedra II. Pacific J. Math. 17(2), 249-262 (1966) · doi:10.2140/pjm.1966.17.249 |
| [15] | Klee, V.: Kleinschmidt P. The \[d\]-step conjecture and its relatives. Math. Oper. Res. 12(4), 718-755 (1987) · Zbl 0632.52007 · doi:10.1287/moor.12.4.718 |
| [16] | Klee, V., Walkup, D.W.: The \[d\]-step conjecture for polyhedra of dimension \[d<6\]. Acta Math. 133, 53-78 (1967) · Zbl 0163.16801 · doi:10.1007/BF02395040 |
| [17] | Matschke, B., Pfeifle, J., Pilaud, V.: Prodsimplicial-neighborly polytopes. Discrete Comput. Geom. 46(1), 100-131 (2011) · Zbl 1223.52005 |
| [18] | Murty, K.G.: The graph of an abstract polytope. Math. Prog. 4, 336-346 (1973) · Zbl 0271.52007 · doi:10.1007/BF01584675 |
| [19] | Pfeifle, J., Pilaud, V., Santos, F.: Polytopality and Cartesian products of graphs. Israel J. Math. (2010). doi:10.1007/s11856-012-0049-5 · Zbl 1257.05142 |
| [20] | Pilaud, V.: Multitriangulations, pseudotriangulations and some problems of realization of polytopes. PhD thesis, École Normale Supérieure Paris and Universidad de Cantabria (2010) · Zbl 0271.52007 |
| [21] | Santos, F.: Personal, communication (2011) |
| [22] | Santos, F.: A counterexample to the Hirsch Conjecture. Ann. Math. 176(1), 383-412 (2012) · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7 |
| [23] | Ziegler, G.M.: Lectures on Polytopes. Number 152 in Graduate Texts in Mathematics. Springer, New York (1994) |
| [24] | Ziegler, G.M.: Projected products of polygons. Electron. Res. Announc. Am. Math. Soc. 10, 122-134 (2004) · Zbl 1068.52014 · doi:10.1090/S1079-6762-04-00137-4 |
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.
