Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
What do you mean by enumerating the possibilities? Do you mean listing the vertices (given some description of the polytope as an intersection of half-spaces, say) or enumerating the types of polytopes? –  Abhinav Kumar Sep 7 '11 at 21:51
1  
Depends on your notion of horrible. Think of adding 6 points to a 9-simplex, where at each stage you have your choice of 9 points from which to choose. That should be at least 10^5 distinct possibilities, so I don't know what you are thinking. Gerhard "Ask Me About System Design" Paseman, 2011.09.07 –  Gerhard Paseman Sep 7 '11 at 21:55
    
The Avis and Fukuda pivoting algorithm is hard to beat. It was cited in this MO question: mathoverflow.net/questions/74779 . See also the Wikipedia article on "the criss-cross algorithm": en.wikipedia.org/wiki/Criss-cross_algorithm . –  Joseph O'Rourke Sep 7 '11 at 21:55
    
Excuse, I mean at each stage you choose 9 out of the available points to add edges. Gerhard "Ask Me About Rewriting Comments" Paseman, 2011.09.07 –  Gerhard Paseman Sep 7 '11 at 21:56
2  
A general upper bound for the number of $n$-vertex polytopes of dimension $d$ appears in projecteuclid.org/…, but I don't think this will be of any use to you. –  Richard Stanley Sep 8 '11 at 1:47
show 3 more comments

3 Answers 3

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.

share|improve this answer
    
Thanks! At least that gives a place to look... –  Igor Rivin Sep 8 '11 at 9:27
add comment

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 happend 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 dont 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-,anifolds 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.)

share|improve this answer
    
In (9), 209015 should be 249015. Also this was extended to 11 vertices by Lutz and Sulanke, Europ J Combin, 30 (2009) 1965-1979. –  Brendan McKay Sep 10 '11 at 6:52
    
Thanks, Brendan. I updated the answer. –  Gil Kalai Sep 10 '11 at 8:30
add comment

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.

share|improve this answer
    
That is very nice, thanks (and I just noticed this...) –  Igor Rivin Sep 21 '13 at 4:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.