Polytopes with few vertices.

Question

Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is there some constructive way to enumerate the possibilities? If the polytope has $k$ vertices, is there some not-too-horrible upper bound on the number of possibilities?

Answer 1

By Gale duality, the possible arrangements of $16$ points in $\mathbb{R}^9$ are in bijection with the arrangements of $16$ points in $\mathbb{R}^5$. See Ziegler, Lectures on Polytopes, Chapter 6 for background on this. In particular, Corollary 6.20 in Ziegler tells you which configurations of 16 points in $\mathbb{R}^5$ are Gale dual to vertices of polytopes.

I don't think you are going to find a listing of all possible combinatorial types of $16$ points in $\mathbb{R}^5$ anywhere. The Oriented Matroid database is collecting this sort of data but, as you can see, the number of isomorphism classes of even 9 points in $\mathbb{R}^5$ is already listed as "unknown".

In short, there are tools to analyze this sort of thing, namely Gale duality and oriented matroids, but a complete list is likely to be out of reach.

Answer 2

It is very difficult to enumerate the combinatorial types of $d$-dimensional polytopes with $n=d+r$ vertices when $d>3$ or when $r>3$. It is also difficult to give good asymptotic upper bounds. Let me mention some results and links.

1. There is a well developed theory largely developed by Tutte to determine the number of 3-polytopes with $n$ vertices, as well as of special type of such polytopes.

2. In dimension 3 Steinitz's theorem asserts that a graph G is the graph of a 3-polytope iff it is 3-connexted and planar and this happens iff G is the graph of a polyhedral complex realizing $S^2$.

3. For $d$-polytopes with $d+3$ vertices a complete enumeration, as well as enumeration of simplicial polytopes was found by Perles based on Gale-transform. Also in this case all simplicial [polyhedral] spheres come from polytopes.

4. When $d>3$ and when $r>3$ there are much more spheres than polytopes. Upper bounds for the numbers of simplicial polytopes, and general polytopes were obtained by Goodman and Pollack (see Stanleys comment above) and Alon respectively. These upper bounds are based on the Milnor-Thom theorem. (Probably they are quite horrible.) Much much huger lower bounds for the number of triangulations of $(d-1)$-dimensional spheres were obtained by me ($d>4$) and Pfeifle and Ziegler ($d=4$). The asymptotic behavior of (log) the number of triangulations of 3-spheres (and manifolds) with $n$ vertices is still unknown.

5. The best known lower bounds for the number of polytopes for general $d$ and $n$ were obtained by Shemer based on a "sewing construction" discovered by him. (A closely related construction was discovered around the same time by Barnette.)

6. Bruckner (1909) enumerated all simplicial 4-polytopes with 8 vertices (this is the first case not falling under 2. and 3.) and his work was completed by Grunbaum and Sridhatan. There are 37 combinatorial types and additional 2 triangulations of $S^3$ which don't come from polytopes.

7. Altshuler and Steinberg enumerated all 4-polytopes with 8 vertices - there are 1294 (and all of them are rational) and all 3-dimensional polyhedral spheres with 8 vertices which are not polytopal - there are 42 of those.

8. Altshuler and Steinberg also enumerated simplicial 3-spheres and manifolds with 9 vertices. There are 1297 combinatorial types of 3-manifolds with 9 vertices; all of them are spheres except one. Of those Altshuler and Steinberg showed that 1090 are polytopal, 142 are non-polytopal and the resy were not decided by them (I vaguely remember that they were all decided later). In these cases it is much harder to determine polytopality then to enumerate the combinatorial types of simplicial spheres. There are various interesting methods to show that a triangulated sphere is not polytopal. Some methods are combinatorial, and some (largely developed by Bokowski and several coauthors) rely on oriented matroid and manipulations of Grassman-Plucker relations. It took several papers until a paper by Altshuler, Bokowski and Steinberg completely classified these 1296 triangulated spheres to 1142 polytopal and 154 nonpolytopal.

9. Frank Lutz found that there are precisely 249015 triangulated 3-manifolds with 10 vertices. 247882 of those are spheres. Lutz and Sulanke showed that there are 172 638 650 triangulated 3-manifolds with 11 vertices. (Again, most of them are spheres.)

10. It is known that the number of simplicial $d$-polytopes with n facets (equivalently the number of simple $d$-polytopes with $n$ vertices) and even the number of shellable triangulations of the $(d-1)$-spheres is only exponential in n namely it is bounded from above by $C_d^n$. This is not known to be either true or false for triangulated spheres.

(It looks that understanding the case asked by Igor and even giving good estimates is beyond reach now. But this may depend on the precise motivation.)

Answer 3

I've got some information about a lower bound.

We know how many binary codes there are of length 5 on n words - http://oeis.org/A034190. Each corresponds to a subset of the vertices of a cube and thus a convex polytope. For length 5 with 16 words we get 169112, and a total of 1,226,525 up to symmetry.

I've computed the flag vectors for all such polytopes in dimension 5 - http://arxiv.org/abs/1011.4269. Including polars I get 688,298 flag vectors. (I did this for a good reason.)

From this calculation I can conclude that in dimension 5 with up to 32 vertices there are at least 344,149 such polytopes that are combinatorially distinct.