Enumerating Neighborly Polytopes and Oriented Matroids

REFERENCES

• [Achterberg 09] T. Achterberg. “SCIP: Solving Constraint Integer Programs.” Math. Program. Comput. 1:1 (2009), 1–41. http://mpc.zib.de/index.php/MPC/article/view/4.
   Google Scholar
• [Adiprasito and Padrol (in press)] K. A. Adiprasito and A. Padrol. “The Universality Theorem for Neighborly Polytopes.” Combinatorica ( in press). preprint available at arXiv:1402.7207.
   Web of Science ®Google Scholar
• [Aichholzer et al. 02] O. Aichholzer, F. Aurenhammer, and H. Krasser. “Enumerating Order Types for Small Point Sets with Applications.” Order. 19:3 (2002), 265–281.
   Web of Science ®Google Scholar
• [Aichholzer and Krasser 07] O. Aichholzer and H. Krasser. “Abstract Order Type Extension and New Results on the Rectilinear Crossing Number.” Comput. Geom. 36:1 (2007), 2–15.
   Web of Science ®Google Scholar
• [Altshuler 77] A. Altshuler. “Neighborly 4-polytopes and Neighborly Combinatorial 3-manifolds with Ten Vertices.” Canad. J. Math. 29:2 (1977), 400–420.
   Web of Science ®Google Scholar
• [Altshuler 80] A. Altshuler, J. Bokowski, and L. Steinberg. “The Classification of Simplicial 3-spheres with Nine Vertices into Polytopes and Nonpolytopes.” Discrete Math. 31:2 (1980), 115–124.
   Web of Science ®Google Scholar
• [Altshuler and McMullen 73] A. Altshuler and P. McMullen. “The Number of Simplicial Neighbourly d-polytopes with d + 3 Vertices.” Mathematika. 20 (1973), 263–266.
   Web of Science ®Google Scholar
• [Altshuler and Steinberg 73] A. Altshuler and L. Steinberg. “Neighborly 4-polytopes with 9 Vertices.” J. Combin. Theory Ser. A. 15 (1973), 270–287.
   Google Scholar
• [Altshuler and Steinberg 85] A. Altshuler and L. Steinberg. “The Complete Enumeration of the 4-polytopes and 3-spheres with Eight Vertices.” Pacific J. Math. 117:1 (1985), 1–16.
   Web of Science ®Google Scholar
• [Babson et al. 01] E. Babson, L. Finschi, and K. Fukuda. “Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids.” Euro. J. Combin. 22:5 (2001), 587–600. (Combinatorial geometries (Luminy, 1999)).
   Web of Science ®Google Scholar
• [Bayardo 97] R. Bayardo. Relsat. “Using CSP Look-Back Techniques to Solve Real-World SAT Instances.” Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, July 27-31, Providence, Rhode Island (1997), 203–208. Available online http://www.aaai.org/Library/AAAI/1997/aaai97-032.php
   Google Scholar
• [Bender and Wormald 88] E. A. Bender and N. C. Wormald. “The Number of Rooted Convex Polyhedra.” Canad. Math. Bull. 31:1 (1988), 99–102.
   Web of Science ®Google Scholar
• [Björner et al. 99] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented Matroids. In Encyclopedia of Mathematics and its Applications, second edition, Vol. 46. Cambridge: Cambridge University Press, 1999.
   Google Scholar
• [Bokowski and Guedes de Oliveira 00] J. Bokowski and A. Guedes de Oliveira. “On the Generation of Oriented Matroids.” Discrete Comput. Geom. 24 (2000), 555–602.
   Web of Science ®Google Scholar
• [Bokowski and Garms 87] J. Bokowski and K. Garms. “Altshuler’s Sphere M10425 is Not Polytopal.” Eur. J. Combin. 8:3 (1987), 227–229.
   Web of Science ®Google Scholar
• [Bokowski and Richter 90a] J. Bokowski and J. Richter. “On the Finding of Final Polynomials.” Eur. J. Combin. 11:1 (1990a), 21–34.
   Web of Science ®Google Scholar
• [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.
   Google Scholar
• [Bokowski and Shemer 87] J. Bokowski and I. Shemer. “Neighborly 6-Polytopes with 10 Vertices.” Israel J. Math. 58:1 (1987), 103–124.
   Web of Science ®Google Scholar
• [Bokowski and Shemer 87] J. Bokowski and B. Sturmfels. “Polytopal and Nonpolytopal Spheres: An Algorithmic Approach.” Israel J. Math. 57:3 (1987), 257–271.
   Web of Science ®Google Scholar
• [Bremner et al. 13] D. Bremner, A. Deza, W. Hua, and L. Schewe. “More Bounds on the Diameters of Convex Polytopes.” Optim. Methods Softw. 28:3 (2013), 442–450.
   Web of Science ®Google Scholar
• [Bremner and Schewe 11] D. Bremner and L. Schewe. “Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets.” Exp. Math. 20:3 (2011), 229–237.
   Web of Science ®Google Scholar
• [Finbow 14] W. Finbow. “Simplicial Neighbourly 5-Polytopes with Nine Vertices.” Boletín de la Sociedad Matemática Mexicana. 21:1 (2014), 39–51.
   Web of Science ®Google Scholar
• [Finschi and Fukuda 02] L. Finschi and K. Fukuda. “Generation of Oriented Matroids—A Graph Theoretical Approach.” Discrete Comput. Geom. 27:1 (2002), 117–136. Geometric combinatorics (San Francisco, CA/Davis, CA, 2000).
   Web of Science ®Google Scholar
• [Finschi and Fukuda 03a] L. Finschi and K. Fukuda. “Combinatorial Generation of Small Point Configurations and Hyperplane Arrangements.” In Discrete and Computational Geometry, Algorithms Combin., pp. 425–440, Vol. 25. Berlin: Springer, 2003.
   Google Scholar
• [Finschi and Fukuda 03b] L. Finschi and K. Fukuda. “Homepage of Oriented Matroids.” Institute for Operations Research, Swiss Federal Institute of Technology, Zurich, Switzerland, 2003 http://www.om.math.ethz.ch/.
   Google Scholar
• [Fukuda et al. 13] K. Fukuda, H. Miyata, and S. Moriyama. “Complete Enumeration of Small Realizable Oriented Matroids.” Discrete Comput. Geom. 49:2 (2013), 359–381.
   Web of Science ®Google Scholar
• [Fusy 06] É. Fusy. “Counting d-Polytopes with d + 3 Vertices.” Electron. J. Combin. 13:1 (2006), Research Paper 23, 25.
   Web of Science ®Google Scholar
• [Gonzalez-Sprinberg and Laffaille 89] G. Gonzalez-Sprinberg and G. Laffaille. “Sur les Arrangements Simples de huit droites dans RP2.” C. R. Acad. Sci. Paris Sér. I Math. 309:6 (1989), 341–344.
   Google Scholar
• [Goodman and Pollack 80] J. E. Goodman and R. Pollack. “On the Combinatorial Classification of Nondegenerate Configurations in the Plane.” J. Combin. Theory Ser. A 29:2 (1980), 220–235.
   Web of Science ®Google Scholar
• [Grünbaum 72] B. Grünbaum. Arrangements and spreads, American Mathematical Society Providence, R.I., Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10, 1972.
   Google Scholar
• [Grünbaum 03] B. Grünbaum. Convex Polytopes, second edition, In Graduate Texts in Mathematics, Vol. 221, Prepared and with a preface by V. Kaibel, V. Klee, and G. M. Ziegler. New York: Springer-Verlag, 2003
   Google Scholar
• [Grünbaum and Sreedharan 67] B. Grünbaum and V. P. Sreedharan. “An Enumeration of Simplicial 4-Polytopes with 8 Vertices.” J. Comb. Theory 2 (1967), 437–465.
   Google Scholar
• [Holmsen et al. 08] A. F. Holmsen, J. Pach, and H. Tverberg. “Points Surrounding the Origin.” Combinatorica 28:6 (2008), 633–644.
   Web of Science ®Google Scholar
• [Kalai 91] G. Kalai. The Diameter of Graphs of Convex Polytopes and f-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.
   Google Scholar
• [Klee 64] V. Klee. “Diameters of Polyhedral Graphs.” Can. J. Math. 16 (1964), 602–614.
   Web of Science ®Google Scholar
• [Klee 66] V. Klee. “Paths on Polyhedra. II.” Pac. J. Math. 17:2 (1966), 249–262.
   Web of Science ®Google Scholar
• [Kortenkamp 97] U. H. Kortenkamp. “Every Simplicial Polytope with at Most d + 4 Vertices is a Quotient of a Neighborly Polytope.” Discrete Comput. Geom. 18:4 (1997), 455–462.
   Web of Science ®Google Scholar
• [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.
   Google Scholar
• [Matsumoto et al. 12] Y. Matsumoto, S. Moriyama, H. Imai, and D. Bremner. “Matroid Enumeration for Incidence Geometry.” Discrete Comput. Geom. 47:1 (2012), 17–43.
   Web of Science ®Google Scholar
• [McKay and Piperno 14] B. McKay and A. Piperno. “Practical graph isomorphism, {II}.” Journal of Symbolic Computation 60 (2014), 94–112. Available online http://cs.anu.edu.au/~bdm/nauty/.
   Web of Science ®Google Scholar
• [McMullen 70] P. McMullen. “The Maximum Numbers of Faces of a Convex Polytope.” Mathematika, Lond. 17:2 (1970), 179–184.
   Google Scholar
• [McMullen 74] P. McMullen. “The Number of Neighbourly d-polytopes with d + 3 Vertices.” Mathematika 21 (1974), 26–31.
   Web of Science ®Google Scholar
• [Mnëv 88] N. E. Mnëv. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties, Topology and Geometry—Rohlin Seminar, Lecture Notes in Math, pp. 527–543, Vol. 1346. Berlin: Springer, 1988.
   Google Scholar
• [Munson 81] B. S. Munson. “Face Lattices of Oriented Matroids.” Ph.D. thesis, Cornell University, 1981.
   Google Scholar
• [Murai and Nevo 13] S. Murai and E. Nevo. “On the Generalized Lower Bound Conjecture for Polytopes and Spheres.” Acta Math. 210:1 (2013), 185–202.
   Web of Science ®Google Scholar
• [Padrol 13] A. Padrol. “Many Neighborly Polytopes and Oriented Matroids.” Discrete Comput. Geom. 50:4 (2013), 865–902.
   Web of Science ®Google Scholar
• [Rambau 02] J. Rambau. “TOPCOM: Triangulations of Point Configurations and Oriented Matroids.” In Mathematical Software—ICMS 2002, edited by A. M. Cohen, X.-S. Gao, and N. Takayama, pp. 330–340. World Scientific, 2002.
   Google Scholar
• [Richter 89] J. Richter. “Kombinatorische Realisierbarkeitskriterien für orientierte Matroide.” Mitt. Math. Sem. Giessen 194 (1989), 112.
   Google Scholar
• [Richter and Sturmfels 91] J. Richter and B. Sturmfels. “On the Topology and Geometric Construction of Oriented Matroids and Convex Polytopes.” Trans. Am. Math. Soc. 325:1 (1991), 389–412.
   Web of Science ®Google Scholar
• [Richter-Gebert 96] J. Richter-Gebert. “Two Interesting Oriented Matroids.” Doc. Math. 1:07 (1996), 137–148.
   Google Scholar
• [Richter-Gebert and Ziegler 95] J. Richter-Gebert and G. M. Ziegler. “Realization Spaces of 4-polytopes are Universal.” Bull. Am. Math. Soc. 32 (1995), 403–412.
   Web of Science ®Google Scholar
• [Rourke and Sanderson 82] C. Patrick Rourke and B. Joseph Sanderson. Introduction to Piecewise-linear Topology, Springer Study Edition. Berlin: Springer-Verlag, 1982, Reprint.
   Google Scholar
• [Santos 02] F. Santos. “Triangulations of Oriented Matroids.” Mem. Am. Math. Soc. 156:741 (2002), viii+80.
   Web of Science ®Google Scholar
• [Santos 12] F. Santos. “A Counterexample to the Hirsch Conjecture.” Ann. Math. (2). 176:(1) (2012), 383–412.
   Web of Science ®Google Scholar
• [Schewe 07] L. Schewe. “Satisfiability Problems in Discrete Geometry.” Ph.D. thesis, Technische Universität Darmstadt, 2007.
   Google Scholar
• [Schuchert 95] P. Schuchert. “Matroid-Polytope und Einbettungen Kombinatorischer Mannigfaltigkeiten.” Ph.D. thesis, TU Darmstadt, 1995.
   Google Scholar
• [Shemer 82] I. Shemer. “Neighborly Polytopes.” Israel J. Math. 43:4 (1982), 291–314.
   Web of Science ®Google Scholar
• [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.
   Google Scholar
• [Sturmfels 88] B. Sturmfels. “Neighborly Polytopes and Oriented Matroids.” Eur. J. Comb. 9:6 (1988), 537–546.
   Web of Science ®Google Scholar
• [Tutte 62] W. T. Tutte. “A New Branch of Enumerative Graph Theory.” Bull. Am. Math. Soc. 68 (1962), 500–504.
   Web of Science ®Google Scholar
• [Wagner 06] U. Wagner. “On a Geometric Generalization of the Upper Bound Theorem.” FOCS (2006) 635–645.
   Google Scholar