Combinatorics – Polytope with Vertices Belonging to All But Two Facets

co.combinatoricsconvex-polytopesdiscrete geometry

Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a Cartesian product of two simplices?

Some remarks

  • by "facet" I mean "face of codimension $1$"
  • a Cartesian product of two simplices has the desired property
  • this is trivially true for $\dim P = 2$
  • this is true for $\dim P = 3$: by playing with the Euler formula and the list of polyhedra with small $f$-vectors, one checks that only the triangular prism satisfies the condition
  • it is a classical fact that a $n$-dimensional simple polytope with $n+2$ facets is a Cartesian product of two simplices. So the answer is positive if $P$ is assumed to be simple.

Best Answer

There are other polytopes with this property that can be obtained via the free join construction.

Given two polytopes $P_1\subset\Bbb R^{d_1}$ and $P_2\subset\Bbb R^{d_2}$, the free join $P_1\bowtie P_2$ is obtained by embedding $P_1$ and $P_2$ into skew affine subspaces of $\Bbb R^{d_1+d_2+1}$ and taking the convex hull.

The claim is that if $P_1$ and $P_2$ have your property, then so does $P_1\bowtie P_2$. To see this, note that the facets of $P_1\bowtie P_2$ are exactly of the form $P_1\bowtie f_2$ and $f_1\bowtie P_2$, where $f_i$ is a facet of $P_i$. Now, if $v$ is a vertex in, say, $P_1\subset P_1\bowtie P_2$ that is in all facets of $P_1$ except for $f,f'\subset P_1$, then $v$ is in all facets of $P_1\bowtie P_2$ except for $f\bowtie P_2$ and $f'\bowtie P_2$. Equivalently for vertices in $P_2$.

Example. Take the free join of two squares, which is a 5-dimensional polytope with 8 vertices, 8 facets and vertex degree 6. This polytope is not simple and can thus not be the cartesian product of two simplices.


This construction yields counterexamples in dimension $d\ge 5$. Concerning $d=4$, there should not be any counterexamples in this dimension.

Suppose that $P\subset\Bbb R^4$ is a counterexample. According to Moritz Firsching's comment we can assume that it has $n\ge 10$ facets. Each vertex is then contained in exactly $n-2\ge 8$ of them. More generally, each set of $k$ vertices is contained in at least $n-2k$ facets. But let $f\subset P$ be a 2-face of $P$ and $v_1,v_2,v_3\in f$ three affinely independent vertices, then this set of vertices, and thus also $f$, is contained in $n-6\ge 4$ facets. This cannot be, since each 2-face of $P$ is contained in exactly two facets.

I believe this generalizes to show that any polytope with your property must have $\le 2d$ facets.

Related Question