Realizability and inscribability for simplicial polytopes via nonlinear optimization. (English) Zbl 1379.52017
Summary: We show that nonlinear optimization techniques can successfully be applied to realize and to inscribe matroid polytopes and simplicial spheres. In order to show non-realizability of simplicial spheres, we extend the method of finding biquadratic final polynomials for matroid polytopes to partial matroid polytopes. Combining these two methods we obtain a complete classification of neighborly polytopes of dimension 4, 6 and 7 with 11 vertices, of neighborly 5-polytopes with 10 vertices, as well as a complete classification of simplicial 3-spheres with 10 vertices into polytopal and non-polytopal spheres. Surprisingly many of the realizable polytopes are also inscribable.
MSC:
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 52B11 | \(n\)-dimensional polytopes |
| 52C40 | Oriented matroids in discrete geometry |
| 90C30 | Nonlinear programming |
Online Encyclopedia of Integer Sequences:
Number of combinatorial types of neighborly 4-polytopes with n vertices.Number of simplicial 3-spheres (triangulations of S^3) with n vertices.
References:
| [1] | Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: a new approach to integrate CP and MIP. In: Perron, L., Trick, M.A. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 5015, pp. 6-20. Springer, Berlin (2008) · Zbl 1142.68504 |
| [2] | Altshuler, A., Bokowski, J., Steinberg, L.: The classification of simplicial \[33\]-spheres with nine vertices into polytopes and nonpolytopes. Discrete Math. 31(2), 115-124 (1980) · Zbl 0468.52008 · doi:10.1016/0012-365X(80)90029-1 |
| [3] | Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1-41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1 |
| [4] | Altshuler, A.: Neighborly 4-polytopes and neighborly combinatorial 3-manifolds with ten vertices. Can. J. Math. 29(225), 420 (1977) · Zbl 0331.57006 |
| [5] | Altshuler, A., McMullen, P.: The number of simplicial neighbourly \[d\] d-polytopes with \[d + 3\] d+3 vertices. Mathematika 20(02), 263-266 (1973) · Zbl 0284.52001 · doi:10.1112/S0025579300004873 |
| [6] | Adiprasito, K.A., Padrol, A., Theran, L.: Universality theorems for inscribed polytopes and Delaunay triangulations. Discrete Comput. Geom. 54(2), 412-431 (2015) · Zbl 1329.52013 · doi:10.1007/s00454-015-9714-x |
| [7] | Altshuler, A., Steinberg, L.: Neighborly 4-polytopes with 9 vertices. J. Comb. Theory Ser A 15(3), 270-287 (1973) · Zbl 0272.52002 · doi:10.1016/0097-3165(73)90074-5 |
| [8] | Altshuler, A., Steinberg, L.: The complete enumeration of the 4-polytopes and 3-spheres with eight vertices. Pac. J. Math. 117(1), 1-16 (1985) · Zbl 0512.52003 · doi:10.2140/pjm.1985.117.1 |
| [9] | Baier, P.: NP-completeness of partial chirotope extendibility (2005). http://arxiv.org/abs/math/0504430 · Zbl 0852.05033 |
| [10] | Bokowski, J., Bremner, D., Gévay, G.: Symmetric matroid polytopes and their generation. Eur. J. Comb. 30(8), 1758-1777 (2009) · Zbl 1229.05060 · doi:10.1016/j.ejc.2008.12.006 |
| [11] | Bagchi, B., Datta, B.: A structure theorem for pseudomanifolds. Discrete Math. 188(1), 41-60 (1998) · Zbl 0951.57012 · doi:10.1016/S0012-365X(97)00273-2 |
| [12] | Bremner, D., Deza, A., Hua, W., Schewe, L.: More bounds on the diameters of convex polytopes. Optim. Methods Softw. 28(3), 442-450 (2013) · Zbl 1266.52016 · doi:10.1080/10556788.2012.668906 |
| [13] | Bokowski, J., Ewald, G., Kleinschmidt, P.: On combinatorial and affine automorphisms of polytopes. Israel J. Math. 47(2-3), 123-130 (1984) · Zbl 0546.52004 · doi:10.1007/BF02760511 |
| [14] | Bokowski, J., de Oliveira, A.G.: Simplicial convex \[44\]-polytopes do not have the isotopy property. Port. Math. 47(3), 309-318 (1990) · Zbl 0714.52005 |
| [15] | Bagnara, R., Hill, P.M., Zaffanella, E.: The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Program. 72(1-2), 3-21 (2008) · doi:10.1016/j.scico.2007.08.001 |
| [16] | Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and its Applications, vol. 46, 2nd edn. Cambridge University Press, Cambridge (1999) · Zbl 0944.52006 |
| [17] | Bokowski, J., Richter, J.: On the finding of final polynomials. Eur. J. Comb. 11(1), 21-34 (1990) · Zbl 0693.05021 · doi:10.1016/S0195-6698(13)80052-2 |
| [18] | Brown, K.Q.: Voronoi diagrams from convex hulls. Inf. Process. Lett. 9(5), 223-228 (1979) · Zbl 0424.68036 · doi:10.1016/0020-0190(79)90074-7 |
| [19] | Brückner, M.: Vielecke und Vielflache: Theorie und Geschichte. Teubner, Leipzig (1900) · JFM 31.0479.04 |
| [20] | Brückner, M.: Über die Ableitung der allgemeinen Polytope und die nach Isomorphismus verschiedenen Typen der allgemeinen Achtzelle (Oktatope), Verhandelingen der Koninklijke Akademie van Wetenschappen te Amsterdam, Afdeeling Natuurkunde. Eerste sectie, vol. 10, pp. 2-27. Johannes Müller, Amsterdam (1909) · Zbl 0631.52009 |
| [21] | Bokowski, J., Shemer, I.: Neighborly 6-polytopes with 10 vertices. Israel J. Math. 58(1), 103-124 (1987) · Zbl 0625.52004 · doi:10.1007/BF02764673 |
| [22] | Bokowski, J., Sturmfels, B.: Computational Synthetic Geometry. Lecture Notes in Mathematics, vol. 1355. Springer, Berlin (1989) · Zbl 0683.05015 |
| [23] | Bokowski, J., Schuchert, P.: Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes. Discrete Comput. Geom. 13(1), 347-361 (1995) · Zbl 0824.52020 · doi:10.1007/BF02574049 |
| [24] | Bremner, D., Schewe, L.: Edge-graph diameter bounds for convex polytopes with few facets. Exp. Math. 20(3), 229-237 (2011) · Zbl 1266.52017 · doi:10.1080/10586458.2011.564965 |
| [25] | Bender, E.A., Wormald, N.C.: The number of rooted convex polyhedra. Can. Math. Bull. 31(1), 99-102 (1988) · Zbl 0649.05034 · doi:10.4153/CMB-1988-015-2 |
| [26] | Dillencourt, M.B., Smith, W.D.: Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161(1-3), 63-77 (1996) · Zbl 0870.05048 · doi:10.1016/0012-365X(95)00276-3 |
| [27] | Donoho, D.L., Tanner, J.: Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102(27), 9452-9457 (2005) · Zbl 1135.60300 · doi:10.1073/pnas.0502258102 |
| [28] | Donoho, D.L., Tanner, J.: Sparse nonnegative solution of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446-9451 (2005) · Zbl 1135.90368 · doi:10.1073/pnas.0502269102 |
| [29] | Eberhard, V.: Zur Morphologie der Polyeder. Teubner, Leipzig (1891) · JFM 23.0544.03 |
| [30] | Euclid. Elementa Geometriae. Erhardus Ratdolt, Venice (1482) · Zbl 1151.57025 |
| [31] | Finschi, L.: A graph theoretical approach for reconstruction and generation of oriented matroids. Ph.D. thesis, Swiss Federal Institute of Technology Zurich (2001) · Zbl 1266.52017 |
| [32] | Finbow, W.: Simplicial neighbourly 5-polytopes with nine vertices. Bol. Soc. Mat. Mex. 21(1), 39-51 (2014) · Zbl 1432.52016 · doi:10.1007/s40590-014-0013-y |
| [33] | Firsching, M.: Computing maximal copies of polyhedra contained in a polyhedron. Exp. Math. 24(1), 98-105 (2015) · Zbl 1315.51017 · doi:10.1080/10586458.2014.956374 |
| [34] | Frick, F., Lutz, F.H, Sullivan, J.M.: Simplicial manifolds with small valence (in preparation) · Zbl 0870.05048 |
| [35] | Fukuda, K., Miyata, H., Moriyama, S.: Complete enumeration of small realizable oriented matroids. Discrete Comput. Geom. 49(2), 359-381 (2013) · Zbl 1278.52014 · doi:10.1007/s00454-012-9470-0 |
| [36] | Frick, F.: A minimal irreducible triangulation of \[S^3\] S3. In: Benedetti, B., Delucchi, E., Moci, L. (eds.) Proceedings of Combinatorial Methods in Topology and Algebra (CoMeTA), Cortona. Springer, Berlin (2013) (to appear) (extended abstract, 4 pages) · Zbl 1135.60300 |
| [37] | Frick, F: Combinatorial restrictions on cell complexes. Dissertation, TU Berlin (2015) · Zbl 0951.57012 |
| [38] | Fusy, É.: Counting \[d\] d-polytopes with \[d+ 3\] d+3 vertices. Electron. J. Comb. 13(1), R23 (2006) · Zbl 1093.52005 |
| [39] | Gale, D.: Neighborly and cyclic polytopes. In: Klee, V. (eds.) Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, vol. 7, pp. 225-232. American Mathematical Society (1963) · Zbl 0137.41801 |
| [40] | Gonska, B., Padrol, A.: Neighborly inscribed polytopes and Delaunay triangulations (2015). arXiv:1308.5798v2 · Zbl 1386.52009 |
| [41] | Grünbaum, B.: Convex Polytopes. Wiley, New York (1967) · Zbl 0163.16603 |
| [42] | Grünbaum, B., Sreedharan, V.P.: An enumeration of simplicial 4-polytopes with 8 vertices. J. Comb. Theory 2(4), 437-465 (1967) · Zbl 0156.43304 · doi:10.1016/S0021-9800(67)80055-3 |
| [43] | Gonska, B., Ziegler, G.M.: Inscribable stacked polytopes. Adv. Geom. 13(4), 723-740 (2013) · Zbl 1288.52007 · doi:10.1515/advgeom-2013-0014 |
| [44] | Hodgson, C.D., Rivin, I., Smith, W.D.: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. Bull. Am. Math. Soc. 27(2), 246-251 (1992) · Zbl 0759.52010 · doi:10.1090/S0273-0979-1992-00303-8 |
| [45] | Kalai, G.: Many triangulated spheres. Discrete Comput Geom. 3(1), 1-14 (1988) · Zbl 0631.52009 · doi:10.1007/BF02187893 |
| [46] | Kleinschmidt, P.: Sphären mit wenigen Ecken. Geom. Dedicata 5(3), 307-320 (1976) · Zbl 0347.52001 · doi:10.1007/BF02414895 |
| [47] | Keith Lloyd, E.: The number of \[d\] d-polytopes with \[d + 3\] d+3 vertices. Mathematika 17(01), 120-132 (1970) · Zbl 0214.02901 · doi:10.1112/S0025579300002795 |
| [48] | Lutz, F.H.: 3-Manifolds. http://page.math.tu-berlin.de/ lutz/stellar/3-manifolds.html · Zbl 0693.05019 |
| [49] | Lutz, F.H.: Combinatorial 3-manifolds with 10 vertices. Beitr. Algebra Geom. 49(1), 97-106 (2008) · Zbl 1151.57025 |
| [50] | Mani, P.: Spheres with few vertices. J. Comb. Theory Ser. A 13(3), 346-352 (1972) · Zbl 0248.52006 · doi:10.1016/0097-3165(72)90068-4 |
| [51] | Montellano-Ballesteros, J.J., Strausz, R.: Counting polytopes via the radon complex. J. Comb. Theory Ser. A 106(1), 109-121 (2004) · Zbl 1042.05024 · doi:10.1016/j.jcta.2004.01.005 |
| [52] | McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17(02), 179-184 (1970) · Zbl 0217.46703 · doi:10.1112/S0025579300002850 |
| [53] | McMullen, P.: The number of neighbourly \[d\] d-polytopes with \[d + 3\] d+3 vertices. Mathematika 21(01), 26-31 (1974) · Zbl 0288.52004 · doi:10.1112/S002557930000574X |
| [54] | Miyata, H.: Database of neighborly polytopes. https://sites.google.com/site/hmiyata1984/neighborly_polytopes · Zbl 1370.52018 |
| [55] | Mnëv, N.E: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. Lecture Notes in Mathematics, vol. 1346, pp. 527-543. Springer, Berlin (1988) · Zbl 0667.52006 |
| [56] | Motzkin, T.S.: Comonotone curves and polyhedra. Bull. Am. Math. Soc. 63, 35 (1957) · doi:10.1090/S0002-9904-1957-10103-7 |
| [57] | Miyata, H., Padrol, A.: Enumerating neighborly polytopes and oriented matroids. Exp. Math. 24(4), 489-505 (2015) · Zbl 1370.52018 · doi:10.1080/10586458.2015.1015084 |
| [58] | Padrol, A.: Many neighborly polytopes and oriented matroids. Discrete Comput. Geom. 50(4), 865-902 (2013) · Zbl 1283.52013 · doi:10.1007/s00454-013-9544-7 |
| [59] | Richter-Gebert, J.: Two interesting oriented matroids. Doc. Math. 1(137), 137-148 (1996) · Zbl 0852.05033 |
| [60] | Richter-Gebert, J., Ziegler, G.M.: Realization spaces of \[44\]-polytopes are universal. Bull. Am. Math. Soc. 32(4), 403-412 (1995) · Zbl 0853.52012 · doi:10.1090/S0273-0979-1995-00604-X |
| [61] | Richter-Gebert, J.; Ziegler, GM; Goodman, JE (ed.); O’Rourke, J. (ed.), Oriented matroids (2004), Boca Raton |
| [62] | Richmond, L.B., Wormald, N.C.: The asymptotic number of convex polyhedra. Trans. Am. Math. Soc. 273 721-735 (1982) · Zbl 0496.05023 |
| [63] | William A.S. et al. Sage Mathematics Software (Version 6.2). The Sage Development Team (2014). http://www.sagemath.org · Zbl 0217.46703 |
| [64] | Schlegel, V.: Über Projectionsmodelle der regelmässigen vier-dimensionalen Körper. Waren (1886) · JFM 18.0456.03 |
| [65] | Schläfli, L.: In: Graf, J.H. (eds.) Theorie der vielfachen Kontinuität, number 38 in Denkschriften der Schweizerischen naturforschenden Gesellschaft. Zürcher & Furrer (1901) · JFM 32.0083.10 |
| [66] | Schmutz, E.: Rational points on the unit sphere. Open Math. 6(3), 482-487 (2008) · Zbl 1176.11037 |
| [67] | Schewe, L.: Nonrealizable minimal vertex triangulations of surfaces: showing nonrealizability using oriented matroids and satisfiability solvers. Discrete Comput. Geom. 43(2), 289-302 (2010) · Zbl 1187.52023 · doi:10.1007/s00454-009-9222-y |
| [68] | Shemer, I.: Neighborly polytopes. Israel J. Math. 43(4), 291-314 (1982) · Zbl 0598.05010 · doi:10.1007/BF02761235 |
| [69] | Shor, P.: Stretchability of pseudolines is NP-hard. In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 531-554. American Mathematical Society (1991) · Zbl 0751.05023 |
| [70] | Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org/ · Zbl 1274.11001 |
| [71] | Steiner, J.: Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander, mit Berücksichtigung der Arbeiten alter und neuer Geometer über Porismen, Projections-Methoden, Geometrie der Lage, Transversalen, Dualität und Reciprocität, etc., vol. 1. Gustav Fincke (1832) · Zbl 0015.36602 |
| [72] | Steinitz, E.; Meyer, F. (ed.); Mohrmann, H. (ed.), Polyeder und Raumeinteilungen, No. 3, 1-139 (1922), Leipzig |
| [73] | Sturmfels, B.: Boundary complexes of convex polytopes cannot be characterized locally. J. Lond. Math. Soc. 2(2), 314-326 (1987) · Zbl 0588.52005 · doi:10.1112/jlms/s2-35.2.314 |
| [74] | Sturmfels, B.: Neighborly polytopes and oriented matroids. Eur. J. Comb. 9(6), 537-546 (1988) · Zbl 0693.05019 · doi:10.1016/S0195-6698(88)80050-7 |
| [75] | Tschirschnitz, F.: Testing extendability for partial chirotopes is NP-Complete. In: Proceedings of the 13th Canadian Conference on Computational Geometry, pp 165-168 (2001) |
| [76] | Tutte, W.T.: On the enumeration of convex polyhedra. J. Comb. Theory Ser. B 28(2), 105-126 (1980) · Zbl 0355.52004 · doi:10.1016/0095-8956(80)90059-3 |
| [77] | Vigerske, S., Gleixner, A.: SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework. Technical Report 16-24, ZIB, Berlin (2016) · Zbl 1398.90112 |
| [78] | Wächter, A., Biegler, T.L.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y |
| [79] | Wiener, C.: Über Vielecke und Vielflache. Teubner, Leipzig (1864) |
| [80] | Ziegler, G.M.: Lectures on Polytopes. Number 152 in Graduate Texts in Mathematics. Springer, Berlin (1995) (updated seventh printing 2007) · Zbl 1093.52005 |
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.
