Enumerating Neighborly Polytopes and Oriented Matroids

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 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 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, ≤12), OM(6, ≤9), OM(7, ≤11), and OM(9, ≤12) 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.

2000 AMS Subject Classification::

• 52B11
• 52C40

Keywords:

• neighborly polytope
• oriented matroid
• enumeration of combinatorial types

Notes

¹This concept should not be confused with the matroid basis polytope, the convex hull of the indicator vectors of bases of a matroid, which is sometimes also called a matroid polytope.

²In the literature, and here, both terms neighborly oriented matroid and neighborly matroid polytope are used interchangeably. We only consider matroid polytopes, but is also natural to define acyclic matroids as 0-neighborly oriented matroids.