4
$\begingroup$

A 01-polytope is the convex hull of some points $S\subseteq\{0,1\}^n$. I wonder, which polytopes can be represented (combinatorially) as 01-polytopes? There are polytopes that cannot have rational coordinates, so those are out. But what about the rest (call them rational polytopes)?

Question: is there a rational polytope that is not combinatorially equivalent to a 01-polytope?

I am fine with embedding a polytope into higher dimension to make it 01.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Doesn’t the number of combinatorial types of (say, simple) polytopes grow too fast for this (I mean, realizing every one as a 01-polytope) to be possible? EDIT: oh, I see, maybe this is what your comment about embedding in higher dimensions was meant to address. $\endgroup$
    – Sam Hopkins
    Commented Sep 8, 2022 at 13:04
  • 1
    $\begingroup$ Embedding in higher dimension does not give you additional 0/1 polytopes. If you have a $d$-polytope $P$ embedded in dimension $n$ for some $n>d$ there are always $n-d$ coordinates that you can forget, to obtain a projection of $P$ in $\mathbb R^d$ with the same combinatorial type. If $P$ was 0/1, the projection still is. $\endgroup$
    – Francisco Santos
    Commented Oct 12, 2022 at 22:55

2 Answers 2

Reset to default
6
$\begingroup$

Rather obvious in retrospect, but all 01-polytopes are inscribed (the vertices lie on a sphere). So if $P$ is non-inscribable, then it can't be a 01-polytope. There are non-inscribable rational polytopes already in dimension three.

Another property of 01-polytopes not shared by all polytopes is that all 2-faces are 3-gons or 4-gons (this is not hard to see but probably proven somwhere in "Lectures on 01-polytopes" by Ziegler). So e.g. the pentagon is not a 01-polytope.

It would be interesting to see an inscribable rational polytope with only 3- and 4-gonal 2-faces that is still not a 01-polytope.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The 24-cell is an inscribable rational polytope with only 3-gonal 2-faces that is still not a 01-polytope. $\endgroup$
    – Daniel Sebald
    Commented Jan 16, 2023 at 20:00
4
$\begingroup$

Every simplicial polytope is rational, hence there are infinitely many rational polytopes in any fixed dimension. In contrast, there are finitely many 0/1 polytopes, since they cannot have more than $2^n$ vertices.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ In theory the “embedding in higher dimensions” remark could get around this obstruction. $\endgroup$
    – Sam Hopkins
    Commented Oct 12, 2022 at 22:11
  • 2
    $\begingroup$ Embedding in higher dimension does not give you additional 0/1 polytopes. If you have a $d$-polytope $P$ embedded in dimension $n$ for some $n>d$ there are always $n-d$ coordinates that you can forget, to obtain a projection of $P$ in $\mathbb R^d$ with the same combinatorial type. If $P$ was 0/1, the projection still is. $\endgroup$
    – Francisco Santos
    Commented Oct 12, 2022 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .