Enumerating neighborly polytopes and oriented matroids. (English) Zbl 1370.52018
Summary: Neighborly polytopes are those that maximize the number of faces in each dimension among all polytopes with the same number of vertices. Despite their extremal properties, they form a surprisingly rich class of polytopes, which has been widely studied and is the subject of many open problems and conjectures.
In this article, we study the enumeration of neighborly polytopes beyond the cases that have been computed so far. To this end, we enumerate neighborly oriented matroids – a combinatorial abstraction of neighborly polytopes – of small rank and corank. In particular, if we denote by \(\mathrm{OM}(r, n)\) the set of all oriented matroids of rank \(r\) and \(n\) elements, we determine all uniform neighborly oriented matroids in \(\mathrm{OM}(5, \leq12)\), \(\mathrm{OM}(6, \leq9)\), \(\mathrm{OM}(7, \leq11)\), and \(\mathrm{OM}(9, \leq12)\) and all possible face lattices of neighborly oriented matroids in \(\mathrm{OM}(6, 10)\) and \(\mathrm{OM}(8, 11)\). Moreover, we classify all possible face lattices of uniform 2-neighborly oriented matroids in \(\mathrm{OM}(7, 10)\) and \(\mathrm{OM}(8, 11)\). Based on the enumeration, we construct many interesting examples and test open conjectures.
In this article, we study the enumeration of neighborly polytopes beyond the cases that have been computed so far. To this end, we enumerate neighborly oriented matroids – a combinatorial abstraction of neighborly polytopes – of small rank and corank. In particular, if we denote by \(\mathrm{OM}(r, n)\) the set of all oriented matroids of rank \(r\) and \(n\) elements, we determine all uniform neighborly oriented matroids in \(\mathrm{OM}(5, \leq12)\), \(\mathrm{OM}(6, \leq9)\), \(\mathrm{OM}(7, \leq11)\), and \(\mathrm{OM}(9, \leq12)\) and all possible face lattices of neighborly oriented matroids in \(\mathrm{OM}(6, 10)\) and \(\mathrm{OM}(8, 11)\). Moreover, we classify all possible face lattices of uniform 2-neighborly oriented matroids in \(\mathrm{OM}(7, 10)\) and \(\mathrm{OM}(8, 11)\). Based on the enumeration, we construct many interesting examples and test open conjectures.
References:
| [1] | DOI: 10.1007/s12532-008-0001-1 · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1 |
| [2] | Adiprasito [Adiprasito and Padrol (in press)] K. A., Combinatorica |
| [3] | DOI: 10.1023/A:1021231927255 · Zbl 1027.68127 · doi:10.1023/A:1021231927255 |
| [4] | DOI: 10.1016/j.comgeo.2005.07.005 · Zbl 1110.65019 · doi:10.1016/j.comgeo.2005.07.005 |
| [5] | DOI: 10.4153/CJM-1977-043-5 · Zbl 0331.57006 · doi:10.4153/CJM-1977-043-5 |
| [6] | DOI: 10.1016/0012-365X(80)90029-1 · Zbl 0468.52008 · doi:10.1016/0012-365X(80)90029-1 |
| [7] | DOI: 10.1112/S0025579300004873 · Zbl 0284.52001 · doi:10.1112/S0025579300004873 |
| [8] | DOI: 10.1016/0097-3165(73)90074-5 · Zbl 0272.52002 · doi:10.1016/0097-3165(73)90074-5 |
| [9] | DOI: 10.2140/pjm.1985.117.1 · Zbl 0512.52003 · doi:10.2140/pjm.1985.117.1 |
| [10] | DOI: 10.1006/eujc.2001.0481 · Zbl 0988.52032 · doi:10.1006/eujc.2001.0481 |
| [11] | Relsat [Bayardo 97] R. Bayardo., Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference pp 203– (1997) |
| [12] | DOI: 10.4153/CMB-1988-015-2 · Zbl 0649.05034 · doi:10.4153/CMB-1988-015-2 |
| [13] | Björner [Björner et al. 99] A., Encyclopedia of Mathematics and its Applications 46 (1999) |
| [14] | DOI: 10.1007/s004540010027 · Zbl 0969.52008 · doi:10.1007/s004540010027 |
| [15] | DOI: 10.1016/S0195-6698(87)80026-4 · Zbl 0636.52008 · doi:10.1016/S0195-6698(87)80026-4 |
| [16] | DOI: 10.1016/S0195-6698(13)80052-2 · Zbl 0693.05021 · doi:10.1016/S0195-6698(13)80052-2 |
| [17] | [Bokowski and Richter 90b] J. Bokowski and J. Richter. ”On the Classification of Non-Realizable Oriented Matroids, Part I: Generation.” Tech. Report Nr. 1283, Technische Hochschule, Darmstadt, 1990b. |
| [18] | DOI: 10.1007/BF02764673 · Zbl 0625.52004 · doi:10.1007/BF02764673 |
| [19] | DOI: 10.1007/BF02766213 · Zbl 0639.52004 · doi:10.1007/BF02766213 |
| [20] | DOI: 10.1080/10556788.2012.668906 · Zbl 1266.52016 · doi:10.1080/10556788.2012.668906 |
| [21] | DOI: 10.1080/10586458.2011.564965 · Zbl 1266.52017 · doi:10.1080/10586458.2011.564965 |
| [22] | DOI: 10.1007/s40590-014-0013-y · Zbl 1432.52016 · doi:10.1007/s40590-014-0013-y |
| [23] | DOI: 10.1007/s00454-001-0056-5 · doi:10.1007/s00454-001-0056-5 |
| [24] | DOI: 10.1007/978-3-642-55566-4_19 · doi:10.1007/978-3-642-55566-4_19 |
| [25] | Finschi [Finschi and Fukuda 03b] L., Institute for Operations Research (2003) |
| [26] | DOI: 10.1007/s00454-012-9470-0 · Zbl 1278.52014 · doi:10.1007/s00454-012-9470-0 |
| [27] | Fusy [Fusy 06] É., Electron. J. Combin. 13 (1) pp 25– (2006) |
| [28] | Gonzalez-Sprinberg [Gonzalez-Sprinberg and Laffaille 89] G., C. R. Acad. Sci. Paris Sér. I Math. 309 (6) pp 341– (1989) |
| [29] | DOI: 10.1016/0097-3165(80)90011-4 · Zbl 0448.05016 · doi:10.1016/0097-3165(80)90011-4 |
| [30] | Grünbaum [Grünbaum 72] B., Arrangements and spreads (10) (1972) · doi:10.1090/cbms/010 |
| [31] | DOI: 10.1007/978-1-4613-0019-9 · Zbl 1024.52001 · doi:10.1007/978-1-4613-0019-9 |
| [32] | DOI: 10.1016/S0021-9800(67)80055-3 · Zbl 0156.43304 · doi:10.1016/S0021-9800(67)80055-3 |
| [33] | DOI: 10.1007/s00493-008-2427-5 · Zbl 1199.52013 · doi:10.1007/s00493-008-2427-5 |
| [34] | [Kalai 91] G. Kalai.The Diameter of Graphs of Convex Polytopes andf-Vector Theory, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 387–411. · Zbl 0739.52017 |
| [35] | DOI: 10.4153/CJM-1964-061-2 · Zbl 0121.37701 · doi:10.4153/CJM-1964-061-2 |
| [36] | DOI: 10.2140/pjm.1966.17.249 · doi:10.2140/pjm.1966.17.249 |
| [37] | DOI: 10.1007/PL00009328 · Zbl 0898.52009 · doi:10.1007/PL00009328 |
| [38] | [Las Vergnas 78] M. Las Vergnas.Extensions ponctuelles d’une géométrie combinatoire orientée, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, pp. 265–270, Vol. 260, Paris: CNRS, 1978. |
| [39] | DOI: 10.1007/s00454-011-9388-y · Zbl 1236.05055 · doi:10.1007/s00454-011-9388-y |
| [40] | DOI: 10.1016/j.jsc.2013.09.003 · Zbl 1394.05079 · doi:10.1016/j.jsc.2013.09.003 |
| [41] | DOI: 10.1112/S0025579300002850 · Zbl 0217.46703 · doi:10.1112/S0025579300002850 |
| [42] | DOI: 10.1112/S002557930000574X · Zbl 0288.52004 · doi:10.1112/S002557930000574X |
| [43] | DOI: 10.1007/BFb0082792 · doi:10.1007/BFb0082792 |
| [44] | [Munson 81] B. S. Munson. ”Face Lattices of Oriented Matroids.” Ph.D. thesis, Cornell University, 1981. |
| [45] | DOI: 10.1007/s11511-013-0093-y · Zbl 1279.52014 · doi:10.1007/s11511-013-0093-y |
| [46] | DOI: 10.1007/s00454-013-9544-7 · Zbl 1283.52013 · doi:10.1007/s00454-013-9544-7 |
| [47] | DOI: 10.1142/9789812777171_0035 · doi:10.1142/9789812777171_0035 |
| [48] | Richter [Richter 89] J., Mitt. Math. Sem. Giessen 194 pp 112– (1989) |
| [49] | DOI: 10.1090/S0002-9947-1991-0994170-3 · doi:10.1090/S0002-9947-1991-0994170-3 |
| [50] | Richter-Gebert [Richter-Gebert 96] J., Doc. Math. 1 (07) pp 137– (1996) |
| [51] | DOI: 10.1090/S0273-0979-1995-00604-X · Zbl 0853.52012 · doi:10.1090/S0273-0979-1995-00604-X |
| [52] | Rourke [Rourke and Sanderson 82] C. Patrick, Introduction to Piecewise-linear Topology (1982) |
| [53] | Santos [Santos 02] F., Mem. Am. Math. Soc. 156 (741) (2002) |
| [54] | DOI: 10.4007/annals.2012.176.1.7 · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7 |
| [55] | [Schewe 07] L. Schewe. ”Satisfiability Problems in Discrete Geometry.” Ph.D. thesis, Technische Universität Darmstadt, 2007. · Zbl 1128.52013 |
| [56] | [Schuchert 95] P. Schuchert. ”Matroid-Polytope und Einbettungen Kombinatorischer Mannigfaltigkeiten.” Ph.D. thesis, TU Darmstadt, 1995. · Zbl 0859.52004 |
| [57] | DOI: 10.1007/BF02761235 · Zbl 0598.05010 · doi:10.1007/BF02761235 |
| [58] | [Shor 91] P. W. Shor.Stretchability of Pseudolines is NP-Hard, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci.pp. 531–554, Vol. 4. Providence, RI: Amer. Math. Soc., 1991. · Zbl 0751.05023 |
| [59] | DOI: 10.1016/S0195-6698(88)80050-7 · Zbl 0693.05019 · doi:10.1016/S0195-6698(88)80050-7 |
| [60] | DOI: 10.1090/S0002-9904-1962-10793-9 · Zbl 0109.41702 · doi:10.1090/S0002-9904-1962-10793-9 |
| [61] | Wagner [Wagner 06] U., FOCS pp 635– (2006) |
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.
