Enumerating neighborly polytopes and oriented matroids

DOI10.1080/10586458.2015.1015084MaRDI QIDQ3194584zbMATH OpenOpenAlexFDO

Authors Hiroyuki Miyata, Arnau Padrol

Publication date 20 October 2015

Published in Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

oriented matroidneighborly polytopeenumeration of combinatorial types

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(10)

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

Describes a project that uses

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)