I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that does not depend on $d$.

I was surprised because I was not aware of this result, which seems quite elementary. Moreover, my proof for it, while simple, is not straightforward. It uses Perles' Skeleton Theorem (see Kalai's paper "Some Aspects Of The Combinatorial Theory Of Convex Polytopes" from 1993).

My questions are:

  • Is this already known?
  • Does it have an elementary proof?

Edit: I uploaded my proof to the arXiv: http://arxiv.org/abs/1503.04129

  • $\begingroup$ Perles' Skeleton Theorem says that the number of k-skeleta of d-polytopes with d+1+a vertices is bounded by a function that does not depend on d. Hence, in principle it deals with low dimensional faces. Taking the polar doesn't help either, because then we lose the bound on the number of vertices. Is there another version of the theorem? $\endgroup$ – Arnau Nov 14 '14 at 15:49
  • $\begingroup$ You may already know this, but your result is reminiscent of the result of Figiel, Lindenstrauss, and Milman (1977) that if a $d$-polytope (1) has $v$ vertices and $f$ facets, (2) contains a unit ball, and (3) is contained in a ball of radius $O(\sqrt d)$, then $(\log v)(\log f) \ge ad$ for some constant $a$. But I'm not sure how to relate combinatorial type to conditions (2) and (3). $\endgroup$ – Timothy Chow Nov 14 '14 at 16:18
  • $\begingroup$ @TimothyChow (2) and (3) is, of course, really only one condition :) $\endgroup$ – Igor Rivin Nov 14 '14 at 18:46
  • $\begingroup$ @TimothyChow yes, I knew this result of Figiel, Lindenstrauss, and Milman. However, I was expecting something more combinatorial and elementary. In fact, the result also holds for some more general lattices that do not come from polytopes (because Perles' Theorem also does). I have the feeling that I am missing some easy argument that uses that there are not so many ways to distribute the $d+1+\alpha$ vertices among the $d+1+\beta$ facets to make the boundary of the polytope. $\endgroup$ – Arnau Nov 15 '14 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.