Enumerating neighborly polytopes and oriented matroids

DOI10.1080/10586458.2015.1015084zbMATH Open1370.52018arXiv1408.0688OpenAlexW1939927341MaRDI QIDQ3194584FDOQ3194584

Authors: Hiroyuki Miyata, Arnau Padrol 

Publication date: 20 October 2015

Published in: Experimental Mathematics (Search for Journal in Brave)

Abstract: 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 paper, 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 OM($r,n$) the set of all oriented matroids of rank $r$ and $n$ elements, we determine all uniform neighborly oriented matroids in OM($5,leq12$), OM($6,leq9$), OM($7,leq11$) and OM($9,leq12$) and all possible face lattices of neighborly oriented matroids in OM($6,10$) and OM($8,11$). Moreover, we classify all possible face lattices of uniform $2$-neighborly oriented matroids in OM($7,10$) and OM($8,11$). Based on the enumeration, we construct many interesting examples and test open conjectures.

Full work available at URL: https://arxiv.org/abs/1408.0688

Recommendations

• Neighborly polytopes and oriented matroids
• Constructing neighborly polytopes and oriented matroids
• Many neighborly polytopes and oriented matroids
• Neighborly polytopes
• Eulerian and bipartite orientable matroids

zbMATH Keywords

oriented matroidneighborly polytopeenumeration of combinatorial types

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Oriented matroids in discrete geometry (52C40)

Cites Work

• SCIP: solving constraint integer programs
• Practical graph isomorphism. II.
• Polytopal and nonpolytopal spheres. An algorithmic approach
• The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
• The complete enumeration of the 4-polytopes and 3-spheres with eight vertices
• Complete enumeration of small realizable oriented matroids
• Neighborly 4-polytopes with 9 vertices
• The Number of Rooted Convex Polyhedra
• Neighborly 4-Polytopes and Neighborly Combinatorial 3-Manifolds with Ten Vertices
• Realization spaces of 4-polytopes are universal
• An enumeration of simplicial 4-polytopes with 8 vertices
• On the finding of final polynomials
• Matroid enumeration for incidence geometry
• Many neighborly polytopes and oriented matroids
• Convex Polytopes
• More bounds on the diameters of convex polytopes
• The maximum numbers of faces of a convex polytope
• Neighborly polytopes
• A counterexample to the Hirsch conjecture
• Title not available (Why is that?)
• On the generalized lower bound conjecture for polytopes and spheres
• Edge-graph diameter bounds for convex polytopes with few facets
• Diameters of Polyhedral Graphs
• Satisfiability problems in discrete geometry
• Abstract order type extension and new results on the rectilinear crossing number
• Altshuler's sphere \(M^{10}_{425}\) is not polytopal
• Every simplicial polytope with at most \(d+4\) vertices is a quotient of a neighborly polytope
• Neighborly 6-polytopes with 10 vertices
• Neighborly polytopes and oriented matroids
• Enumerating order types for small point sets with applications
• On the generation of oriented matroids
• On the combinatorial classification of nondegenerate configurations in the plane
• Title not available (Why is that?)
• Points surrounding the origin
• The number of simplicial neighbourly d ‐polytopes with d +3 vertices
• Cocircuit graphs and efficient orientation reconstruction in oriented matroids
• The number of neighbourly d ‐polytopes with d +3 vertices
• Title not available (Why is that?)
• A new branch of enumerative graph theory
• Simplicial neighbourly 5-polytopes with nine vertices

Cited In (10)

• Neighborly polytopes and oriented matroids
• Transversals and colorings of simplicial spheres
• Small covers and quasitoric manifolds over neighborly polytopes
• Realizability and inscribability for simplicial polytopes via nonlinear optimization
• Complete enumeration of small realizable oriented matroids
• Eulerian and bipartite orientable matroids
• Six topics on inscribable polytopes
• General non-realizability certificates for spheres with linear programming
• Constructing neighborly polytopes and oriented matroids
• On \(k\)-neighborly reorientations of oriented matroids

Uses Software

• nauty
• SCIP
• TOPCOM
• relsat

This page was built for publication: Enumerating neighborly polytopes and oriented matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194584)