1 Introduction
We denote by
$f_{k}$
the number of
$k$
-faces in a polytope; the f-vector of a
$d$
-polytope is the sequence
$(f_0,\ldots , f_{d-1})$
of the number of faces in the polytope. Xue’s theorem settling Grünbaum’s 1967 conjecture [Reference Grünbaum5, Section 10.2] reads as follows.
Theorem 1.1 (
$d$
-polytopes with at most
$2d$
vertices, Xue 2021)
Let
$d\geqslant 2$
and
$1\leqslant s \leqslant d$
. If
$P$
is a
$d$
-polytope with
$d+s$
vertices, then
Furthermore, if
$k\in [1, d-2]$
and
$f_k(P)=\phi _k(d+s,d)$
, then
$P$
is (combinatorially) unique and has exactly
$d+2$
facets.
Naturally, one wants to extend this result to
$d$
-polytopes with more than
$2d$
vertices:
$(d-1)$
-polytopes with at most
$2(d-1)$
vertices have featured prominently as potential facets in the proofs of such results. Lower bound theorems for
$d$
-polytopes with
$2d+1$
vertices [Reference Pineda-Villavicencio and Yost13, Reference Xue15] (see also Theorem 2.4) and
$2d+2$
vertices [Reference Pineda-Villavicencio, Tritama, Wang and Yost8], reveal an interesting dichotomy: minimizers may have either
$d+2$
or
$d+3$
facets. Pineda-Villavicencio [Reference Pineda-Villavicencio7, Problem 8.7.11] conjectured that this dichotomy extends to minimizers of the number of
$k$
-faces among
$d$
-polytopes with at most
$3d-1$
vertices. (This conjecture has recently been proved; see [Reference Pineda-Villavicencio and Wang12]. The main result in the present article serves as an important ingredient.)
In light of these results, we find it natural to investigate this dichotomy for
$d$
-polytopes with
$2d$
or fewer vertices. That is, we determine the minimizers of
$f_k$
amongst all
$d$
-polytopes with at most
$2d$
vertices and at least
$d+3$
facets. Our main theorem thus furnishes a refinement of Theorem 1.1. It will be stated in more detail and proved in subsequent sections.
Since this expression will appear frequently, it is convenient to define
Theorem 1.2 (Refined theorem for
$d$
-polytopes with at most
$2d$
vertices (short version))
Given parameters
$d\geqslant 3$
and
$2\leqslant s \leqslant d$
, and a
$d$
-polytope
$P$
with
$d+s$
vertices, the following statements hold:
-
(i) If $s=2$
and
$P$
has at least
$d+\ell $
facets where
$\ell \in [3, d]$
, then
$f_k(P)\geqslant \phi _k(d+2,d)+\binom {d-1}{k-1}-\binom {d-\ell +1}{k-\ell +1}$
for all
$k\in [1, d-2]$
. Moreover, for each
$k\geqslant \ell -1,$
there is a unique polytope whose number of
$k$
-faces equals this lower bound. -
(ii) If $s\in [3, d]$
and
$P$
has at least
$d+3$
facets, then
$f_k(P)\geqslant \zeta _k(d+s,d)$
. There are two fundamental examples for which the number of
$k$
-faces equals
$\zeta _k(d+s,d)$
for each
$k\in [1, d-2]$
. Additionally, if
$s<d$
and
$k\geqslant d-s+2$
, then a third minimizer arises, and when
$s=4$
, two further examples appear.
A full version of Theorem 1.2, describing the minimizing polytopes in detail, is provided at the beginning of Section 3.
2 Minimizers
This section presents the minimizers in Theorems 1.1 and 1.2.
The
$m$
-dimensional simplex will be denoted by
$T(m)$
. A prism based on
$T(d-1)$
is called a simplicial
$d$
-prism; we will often refer to them simply as prisms. When we need to discuss other prisms, the base will be clearly specified. When
$k\in [1, d-2]$
, each minimizer in Theorem 1.1 is a
$(d-s)$
-fold pyramid over a simplicial
$s$
-prism for
$s\in [1, d]$
; this polytope is called the
$(s,d-s)$
-triplex and denoted by
$M(s,d-s)$
. Triplices were introduced by Pineda-Villavicencio et al. [Reference Pineda-Villavicencio, Ugon and Yost10, Section 3]. Each triplex has
$d+2$
facets. The structure of
$d$
-polytopes with
$d+2$
facets is well understood (see, for instance, [Reference Grünbaum5, Section 6.1]). We will use the formulation provided by McMullen and Shephard [Reference McMullen and Shephard6, Section 3].
Lemma 2.1 (McMullen and Shephard 1970)
Let
$P$
be a
$d$
-dimensional polytope with
$d+2$
facets, where
$d\geqslant 2$
. Then, there exist integers
$2\leqslant a\leqslant d$
and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor $
such that
$P$
is a
$(d-a)$
-fold pyramid over
$T(m)\times T(a-m)$
. The number of
$k$
-faces of
$P$
is
In particular,
$f_{0}(P)=d+1+m(a-m)$
.
Recall that the Cartesian product of a
$d$
-polytope
$P\subset \mathbb {R}^{d}$
and a
$d'$
-polytope
$P'\subset \mathbb {R}^{d'}$
is the Cartesian product of the sets
$P$
and
$P'$
:
Dually to Lemma 2.1, we have a lemma for
$d$
-polytopes with
$d+2$
vertices, which is from Grünbaum [Reference Grünbaum5, Section 6.1]. The direct sum
$P\oplus P'$
of a
$d$
-polytope
$P\subset \mathbb {R}^{d}$
and a
$d'$
-polytope
$P'\subset \mathbb {R}^{d'}$
with the origin in their relative interiors is the
$(d+d')$
-polytope:
Lemma 2.2 Let
$P$
be a
$d$
-dimensional polytope with
$d+2$
vertices, where
$d\geqslant 2$
. Then, there exist integers
$2\leqslant a\leqslant d$
and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor $
such that
$P$
is a
$(d-a)$
-fold pyramid over
$T(m)\oplus T(a-m)$
. The number of
$k$
-dimensional faces of
$P$
is
In particular,
$f_{d-1}(P)=d+1+m(a-m)$
.
As Grünbaum [Reference Grünbaum5, Section 6.1], we denote the
$(d-a)$
-fold pyramid over
$T(m)\oplus T(a-m)$
by
$T_{m}^{d,d-a}$
.
Grünbaum [Reference Grünbaum5, p. 101] established inequalities for the number of
$k$
-faces in
$d$
-polytopes with
$d+2$
vertices.
Lemma 2.3 For
$k\in [0, d-1]$
, the following hold:
-
(i) If $2\leqslant a\leqslant d$
and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor -1$
, then
$f_{k}(T_{m}^{d,d-a})\leqslant f_{k}(T_{m+1}^{d,d-a})$
, with strict inequality if and only if
$m\leqslant k$
. -
(ii) If $2\leqslant a\leqslant d-1$
and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor $
, then
$f_{k}(T_{m}^{d,d-a})\leqslant f_{k}(T_{m}^{d,d-(a+1)})$
, with strict inequality if and only if
$a-m\leqslant k$
.
A vertex
$v$
in a
$d$
-polytope
$P$
is simple if it is contained in exactly
$d$
edges. Otherwise, it is nonsimple. A nonsimple vertex in
$P$
may be simple in a proper face of
$P$
, and we often need to make this distinction. If
$K$
is a closed halfspace in
$\mathbb {R}^d$
whose boundary does not contain any vertices of
$P$
and such that
$v$
is the only vertex of
$P$
not in
$K$
, we say that a polytope
$P'$
is obtained by truncating v if
$P'=P\cap K$
.
If we truncate a simple vertex from the
$(2,d-2)$
-triplex (
$d\geqslant 2$
), we obtain a
$d$
-polytope
$P\hskip -1.6pt m(d)$
whose number of faces is
Pineda-Villavicencio and Yost [Reference Pineda-Villavicencio and Yost13], also [Reference Pineda-Villavicencio, Ugon and Yost9], called the
$d$
-polytope
$P\hskip -1.6pt m(d)$
the d-pentasm.
Theorem 2.4 [Reference Pineda-Villavicencio and Yost13, Theorem 25] and [Reference Xue15, Theorem 5.1]
Let
$d\geqslant 4$
,
$P$
a
$d$
-polytope with at least
$2d+1$
vertices, and
$k\in [1, d-2]$
.
-
(i) If $P$
has at least
$d+3$
facets, then
$f_{k}(P)\geqslant f_{k}(P\hskip -1.6pt m(d))$
, with equality for some
$k\in [1, d-2]$
only if
$P=P\hskip -1.6pt m(d)$
. -
(ii) If $P$
has
$d+2$
facets, then
$f_{k}(P)\geqslant f_{k}((T_{2}^{d,d-(\lfloor {d/2}\rfloor +2)})^{*})$
. If
$d$
is even, then
$(T_{2}^{d,d-(\lfloor {d/2}\rfloor +2)})^{*}$
has
$2d+1$
vertices and this bound can be attained.
Since it appears frequently, it will be convenient to denote the
$a$
-fold pyramid over a
$b$
-pentasm, by
$P\hskip -1.6pt m(b,a)$
. We will denote as usual the pyramid over an arbitrary polytope
$P$
by
$\operatorname {\mathrm {pyr}}(P)$
and the
$t$
-fold pyramid over
$P$
by
$\operatorname {\mathrm {pyr}}_t(P)$
.
The number of
$k$
-faces in the polytope
$P\hskip -1.6pt m(s-1, d+1-s)$
is obtained by counting the
$k$
-faces among the
$d+1-s$
apices of the pyramid and the
$k$
-faces obtained from an
$i$
-face in an
$(s-1)$
-pentasm and
$k-i$
vertices from the
$d+1-s$
apices of the pyramid,
$0 \leqslant i \leqslant k$
. That is, for
$k\in [0, d-1]$
, we have that
Let us compare this expression with the function
$\zeta _k(d+s,d)$
. The following three identities are routine to establish:
Comparing these expressions with the definition of
$\zeta _k$
, we arrive at the following relation:
The wedge construction will be very useful to us. Let
$P$
be a
$d$
-polytope embedded in the hyperplane
$x_{d+1}=0$
of
$\mathbb {R}^{d+1}$
. Let
$F$
be a proper face of
$P$
, and let
$C$
be the halfcylinder
$P\times [0,\infty )\subset \mathbb {R}^{d+1}$
. We cut the halfcylinder with a hyperplane
$H'$
through
$F\times \{0\}$
so that
$C$
is partitioned into two parts, one bounded and one unbounded. The wedge of
$P$
at
$F$
is the bounded part; it is denoted by
$\operatorname {\mathrm {W}}_{F}(P)$
. The sets
$P$
and
$H'\cap C$
, the bases of
$\operatorname {\mathrm {W}}_{F} (P)$
, define facets of
$\operatorname {\mathrm {W}}_{F} (P)$
that are combinatorially isomorphic to
$P$
and intersect at the face
$F\times \{0\}$
. The wedge
$W$
over a
$d$
-polytope
$P\times \{0\}\subseteq \mathbb {R}^{d+1}$
at a face
$F\times \{0\}$
of
$P\times \{0\}$
is combinatorially isomorphic to a prism
$Q$
over
$P\times \{0\}$
where the face prism
$(F\times \{0\})$
of
$Q$
has collapsed into
$F\times \{0\}$
. For further information, refer to [Reference Pineda-Villavicencio7, Section 2.6]. The following basic facts about wedges will be used several times. Their proofs are routine.
Lemma 2.5 Let
$\operatorname {\mathrm {W}}_{F}(P)$
be a wedge of a
$d$
-polytope
$P$
at a face
$F$
of
$P$
.
-
(i) A $k$
-face of
$\operatorname {\mathrm {W}}_{F}(P)$
is either a
$k$
-face of one of the bases of
$\operatorname {\mathrm {W}}_{F}(P)$
, or the wedge of a
$(k-1)$
-face
$F'$
of P at the proper face
$F\cap F'$
, or a prism over a
$(k-1)$
-face of
$P$
disjoint from
$F$
. -
(ii) If $F$
is a facet, then for each value of
$k\in [0,d+1],$
we have $$ \begin{align*}f_k(\operatorname{\mathrm{W}}_{F}(P))=2f_k(P)+f_{k-1}(P)-f_k(F)-f_{k-1}(F).\end{align*} $$
-
(iii) If $W_1,P_1,F_1$
denote pyramids over
$\operatorname {\mathrm {W}}_{F}(P),P,F$
, respectively, then
$W_1$
is combinatorially equivalent to
$\operatorname {\mathrm {W}}_{F_1}(P_1)$
.
We let
$T\hskip -1.6pt A(2)$
be a quadrilateral and let
$T\hskip -1.6pt A(3)$
be the tetragonal antiwedge, the unique nonpyramidal 3-polytope with six vertices and six 2-faces (four triangles and two quadrilaterals) (see Figure 1(a)). For
$d\geqslant 4$
, we iteratively define the
$d$
-polytope
$T\hskip -1.6pt A(d)$
as the wedge of
$T\hskip -1.6pt A(d-1)$
at a facet
$T\hskip -1.6pt A(d-2)$
of
$T\hskip -1.6pt A(d-1)$
. The polytope
$T\hskip -1.6pt A(d)$
has
$T\hskip -1.6pt A(d-1)$
as a facet, and thus this construction is sound (see Figure 1(c)).
Schlegel diagrams of polytopes. (a) The tetragonal antiwedge. (b) The 4-polytope
$W\hskip -1.6pt P$
. (c) The 4-polytope
$T\hskip -1.6pt A(4)$
. (d) The 4-polytope
$Z(4)$
.
Remark 2.6 (Structure of
$T\hskip -1.6pt A(d)$
)
The polytope
$T\hskip -1.6pt A(d)$
has
$2d$
vertices. It has one vertex
$v$
with maximum degree
$2d-2$
,
$d-2$
vertices with degree
$d+1$
, and every other vertex is simple. Its
$d+3$
facets are as follows:
-
(i) $d-2$
copies of
$T\hskip -1.6pt A(d-1)$
; -
(ii) three simplices;
-
(iii) one simplicial $(d-1)$
-prism; -
(iv) one $M(d-2,1)$
.
The facets not containing
$v$
are the prism and one of the simplices.
The polytope
$T\hskip -1.6pt A(d)$
and a pyramid over a
$(d-1)$
-pentasm have the same
$f$
-vector. This follows from noticing that the pyramid over the pentagon (the 2-pentasm) and the tetragonal antiwedge
$T\hskip -1.6pt A(3)$
both have
$f$
-vector
$(6,10,6)$
and that a pyramid over a
$(d-1)$
-pentasm is a wedge of a pyramid over a
$(d-2)$
-pentasm at a facet that is itself a pyramid over
$(d-3)$
-pentasm. In particular, the
$f$
-vectors of the four-dimensional
$T\hskip -1.6pt A(4)$
and a pyramid over
$P\hskip -1.6pt m(3)$
are both
$(8,18,17,7)$
, which serves as a base for induction arguments (see also Proposition 3.4). As a consequence, a
$(d-s)$
-fold pyramid over the
$s$
-polytope
$T\hskip -1.6pt A(s)$
, denoted by
$T\hskip -1.6pt A(s,d-s)$
, and the
$d$
-polytope
$P\hskip -1.6pt m(s-1, d+1-s)$
both have the same
$f$
-vector:
We will see that, for fixed
$s\in [3, d]$
, the polytopes
$T\hskip -1.6pt A(s,d-s)$
and
$P\hskip -1.6pt m(s-1, d+1-s)$
minimize the number of
$k$
-faces for every
$k\in [1, d-2]$
. For many values of
$s$
and
$k$
, these are the only two minimizers. But for some values of
$s$
and
$k$
, there may be up to three more.
Consider
$s=d=4$
. The polytopes
$T\hskip -1.6pt A(4)$
and
$P\hskip -1.6pt m(3, 1)$
both have
$f$
-vector
$(8,18,17,7)$
. The wedge of a square pyramid at one of its edges also has
$f$
-vector
$(8,18,17,7)$
; the combinatorial type depends on whether or not the edge contains the apex of the pyramid. If the edge is in the base of the pyramid, we obtain the example called Polytope 2 in [Reference Pineda-Villavicencio, Ugon and Yost11, Lemma 18(ii)]; here, we denote this 4-polytope by
$W\hskip -1.6pt P$
. If the edge contains the apex, then Lemma 2.5 tells us the polytope is a pyramid over the wedge of a square at one of the vertices; we use
$\Sigma (3)$
to denote the wedge of a square at one of the vertices.Footnote
1
Therefore, for
$s=4$
,
$\operatorname {\mathrm {pyr}}_{d-4}(W\hskip -1.6pt P)$
(the
$(d-4)$
-fold pyramid over
$W\hskip -1.6pt P$
) and
$\operatorname {\mathrm {pyr}}_{d-3}(\Sigma (3))$
(the
$(d-3)$
-fold pyramid over
$\Sigma (3)$
) also minimize the number of
$k$
-faces for every
$k\in [1, d-2]$
.
Let
$Z(3)$
be a triangular bipyramid and let
$Z(2)$
be a triangular face of
$Z(3)$
. For
$d\geqslant 4$
, we define
$Z(d)$
inductively by
$Z(d+1):=\operatorname {\mathrm {W}}_{Z(d-1)}(Z(d))$
.
Remark 2.7 (Structure of
$Z(d)$
)
The polytope
$Z(d)$
is
$d$
-dimensional with
$2d-1$
vertices and
$d+3$
facets. It has two vertices, say
$v$
and
$w$
, with maximum degree
$2d-2$
,
$d-2$
vertices with degree
$d+1$
, and
$d-1$
simple vertices. The
$d+3$
facets are
-
(i) $d-2$
copies of
$Z(d-1)$
; -
(ii) three simplices;
-
(iii) two copies of $M(d-2,1)$
.
The facets not containing
$v$
are one of the
$M(d-2,1)$
copies and one of the simplices. The facets not containing
$w$
are the other
$M(d-2,1)$
copy and another one of the simplices (see Figure 1(d)).
The next result says that the polytope
$Z(d)$
minimizes
$f_k$
among
$d$
-polytopes with
$2d-1$
vertices and at least
$d+3$
facets only for
$k\geqslant 3$
.
Lemma 2.8 For
$d\geqslant 2$
, the
$f$
-vector of the polytope
$Z(d)$
is given by
In particular,
$f_2(Z(d))=\zeta _2(2d-1,d)+1$
, and
$f_k(Z(d))=\zeta _k(2d-1,d)$
for
$k\geqslant 3$
.
Proof Since
$Z(3)$
has exactly two more vertices than
$Z(2)$
, the expression for
$f_{0}$
is clear. An induction argument on
$d\geqslant 3$
establishes that
$f_1(Z(d))=(d-2)^2+5(d-2)+3$
. Similarly, the expression
$f_2(Z(d))=\frac {1}{3}(d^3-4d+3)$
can be proved by induction on
$d$
, starting with the base cases
$d=2,3$
; the induction step uses the expression for
$f_{1}$
and Lemma 2.5.
For computing
$f_{k}$
for
$k\geqslant 3$
, we proceed again by induction on
$d\geqslant 3$
for all
$k$
, with
$d=4,3$
as the base cases. Suppose the conclusion is valid up to dimension
$d$
. Repeated applications of Pascal’s identity yield
Hence, the conclusion is also valid in dimension
$d+1$
.
We are also interested in the
$(d-s-1)$
-fold pyramid over
$Z(s+1)$
, denoted by
$Z(s+1,d-s-1)$
, which has
$d+s$
vertices and
$d+3$
facets. If
$P$
is a pyramid over a facet
$F$
, then
$f_k(P)=f_k(F)+f_{k-1}(F)$
for each
$k\geqslant 0$
. Iteration of this leads to the following conclusion for the
$(d-s-1)$
-fold pyramid over
$Z(s+1)$
:
-
(i) If $s<d-1$
, then the expression for
$f_k$
only involves terms of the form
$f_j$
with
$3\leqslant j\leqslant k$
, leading to
$f_k(Z(s+1,d-s-1))=\zeta _k(d+s,d)$
for
$k\geqslant d-s+2$
. -
(ii) However, for $k\leqslant d-s+1$
, we have
$f_k(Z(s+1,d-s-1))=\zeta _k(d+s,d)+1$
.
Thus,
$Z(s+1,d-s-1)$
minimizes the number of
$k$
-faces among
$d$
-polytopes with at least
$d+3$
facets and exactly
$d+s$
(
$3\leqslant s \leqslant d$
) vertices only for
$k\in [d-s+2,d-1]$
.
3 Proof of the main theorem
We list the full version of the main theorem.
Theorem 3.1 (Refined theorem for
$d$
-polytopes with at most
$2d$
vertices)
Given parameters
$d\geqslant 3$
and
$2\leqslant s \leqslant d$
, and a
$d$
-polytope
$P$
with
$d+s$
vertices, the following statements hold:
-
(i) If $s=2$
, then
$P$
has the form
$T_{m}^{d,d-a}$
for some
$2\leqslant a\leqslant d$
and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor $
. If
$P$
has at least
$d+\ell $
facets, where
$\ell \in [3, d]$
, then for all
$k\in [1, d-2]$
, $$ \begin{align*} f_k(P)\geqslant \phi_k(d+2,d)+\binom{d-1}{k-1}-\binom{d-\ell+1}{k-\ell+1}. \end{align*} $$
Moreover, if $m=1$
and
$P\ne T_{1}^{d,d-\ell }$
, then
$f_k(P)>f_k(T_{1}^{d,d-\ell })$
, for each
$k\geqslant \ell -1$
. If
$m\geqslant 2$
, then
$f_k(P)>f_k(T_{1}^{d,d-\ell })$
, for each
$k\in [1, d-2]$
. -
(ii) If $s\in [3, d]$
and
$P$
has at least
$d+3$
facets, then
$f_k(P)\geqslant \zeta _k(d+s,d)$
. Additionally, if
$k\in [1, d-2]$
, and
$P$
is a
$d$
-polytope whose number of
$k$
-faces equals
$\zeta _k(d+s,d)$
, then either-
(a) $P$
is a
$(d-s+1)$
-fold pyramid over an
$(s-1)$
-pentasm, or -
(b) $P$
is a
$(d-s)$
-fold pyramid over
$T\hskip -1.6pt A(s)$
, or -
(c) $s<d$
,
$k\geqslant d-s+2$
, and
$P$
is a
$(d-s-1)$
-fold pyramid over
$Z(s+1)$
, or -
(d) $s=4$
, and
$P$
is a
$(d-3)$
-fold pyramid over
$\Sigma (3)$
, or -
(e) $s=4$
, and
$P$
is a
$(d-4)$
-fold pyramid over
$W\hskip -1.6pt P$
.
-
We start from the beginning, at
$d$
-polytopes with
$d+2$
vertices. This theorem is a variation of the dual statement in Theorem 1.1.
Theorem 3.2 (
$d+2$
vertices)
Let
$d\geqslant 3$
,
$2\leqslant \ell ,a\leqslant d$
, and
$1\leqslant m\leqslant \lfloor {a/2}\rfloor $
. Let
$P:=T_{m}^{d,d-a}$
be a
$d$
-polytope with at least
$d+\ell $
facets, other than
$T_{1}^{d,d-\ell }$
. The following hold:
-
(i) If $m=1$
, then
$f_k(P)>f_k(T_{1}^{d,d-\ell })$
, for each
$k\geqslant \ell -1$
. -
(ii) If $m\geqslant 2$
, then
$f_k(P)>f_k(T_{1}^{d,d-\ell })$
, for each
$k\in [1, d-2]$
.
Proof If
$m=1$
, Lemma 2.2 gives
$f_{d-1}(P)=d+1+m(a-m)=d+a$
. Since
$P\ne T_{1}^{d,d-\ell }$
, we have that
$a>\ell $
, in which case Lemma 2.3(ii) gives that
$f_k(P)>f_k(T_{1}^{d,d-\ell })$
, for each
$k\geqslant \ell -1$
. Henceforth, we assume that
$m\geqslant 2$
. We prove (ii) by an induction argument on
$d\geqslant 3$
for all
$a,\ell \in [2, d]$
and
$2\leqslant m\leqslant \lfloor {a/2}\rfloor $
. The case
$d=3$
is simple. We then assume that
$d\geqslant 4$
,
$f_{d-1}(P)\geqslant d+\ell $
, and that (ii) holds for all
$(d-1)$
-polytopes
$T_{m'}^{d-1,d-a'-1}$
with at least
$d-1+\ell '$
facets for all
$a',\ell '\in [2, d-1]$
and
$2\leqslant m'\leqslant \lfloor {a'/2}\rfloor $
.
Lemma 2.3(i) yields that
$f_{k}(T_1^{d,d-\ell })<f_{k}(T_2^{d,d-\ell })$
, for each
$k\geqslant 1$
. Additionally, when
$\ell \leqslant a$
, Lemma 2.3 gives that
Hence, for
$k\in [1, d-2]$
and
$\ell \leqslant a$
, we get that
$f_{k}(T_1^{d,d-\ell })<f_{k}(T_m^{d,d-a})$
.
We now assume that
$d\geqslant \ell>a$
. Hence,
$P$
is a pyramid with base
$F:=T_m^{d-1,d-1-a}$
, where
$a\in [2, d-1]$
and
$m\geqslant 2$
. The induction hypothesis holds for
$F$
when
$\ell \in [2, d-1]$
, since
$F$
has
$d-1+2$
vertices and at least
$d-1+\ell (d-2)$
-faces. As a consequence, for each
$k\in [1, d-2]$
, we find that
For the case
$f_{d-2}(P)$
, we remark that
$f_{d-2}(F)\geqslant d-1+\ell =f_{d-2}(T_{1}^{d-1,d-1-\ell })$
by assumption and that
$f_{d-3}(F)>f_{d-3}(T_{1}^{d-1,d-1-\ell })$
by induction.
Suppose
$\ell =d$
. Then
$f_{d-2}(F)\geqslant d-1+\ell \geqslant 2(d-1)$
, and thus, for each
$k\in [1, d-2],$
the induction hypothesis on
$d-1$
for
$\ell '= d-1$
gives that
This completes the proof of the theorem.
Proposition 3.3 [Reference Xue14, Proposition 3.1]
Let
$d\geqslant 2$
and let
$P$
be a
$d$
-polytope. In addition, suppose that
$r\leqslant d+1$
is given and that
$S:=(v_1,v_2,\ldots ,v_r)$
is a sequence of distinct vertices in
$P$
. Then the following hold:
-
(i) There is a sequence $F_1, F_2,\ldots , F_r$
of faces of
$P$
such that each
$F_i$
has dimension
$d-i+1$
and contains
$v_i$
, but does not contain any
$v_j$
with
$j<i$
. -
(ii) For each $k\geqslant 1$
, the number of
$k$
-faces of
$P$
that contain at least one of the vertices in
$S$
is bounded from below by $$ \begin{align*} \sum_{i=1}^{r}f_{k-1}(F_i/v_i)\geqslant \sum_{i=1}^{r} \binom{d+1-i}{k}. \end{align*} $$
-
(iii) In case of equality in (ii) for some $k\in [1, d-2]$
, then for any ordering
$v_{\ell 1},\ldots ,v_{\ell r}$
of the vertices of
$S$
, we must have that the number of
$k$
-faces containing
$v_{\ell i}$
and not containing any vertex
$v_{\ell j}$
with
$j<i$
is precisely
$\binom {d-i+1}{k}$
. In particular, every vertex in
$S$
is simple.
Proof Statements (i) and (ii) are from [Reference Xue14, Proposition 3.1]. Part (iii) is proven in [Reference Pineda-Villavicencio7, Corollary 8.2.6]; it follows from noting that the minimum of the right-hand side is attained when each vertex figure
$F_{i}/v_{\ell i}$
is a
$(d-i)$
-simplex.
We now deal with dimensions 3 and 4 in Theorem 3.1.
Proposition 3.4 For
$d=3$
or
$4$
and
$3\leqslant s\leqslant d$
, the
$d$
-polytopes with precisely
$d+s$
vertices, at least
$d+3$
facets, and at most
$\zeta _k(d+s,d)\; k$
-faces for each
$k\in [1, d-2]$
, are as follows:
-
(i) For $d=3$
, the minimizers are
$T\hskip -1.6pt A(3)$
and the pyramid over the pentagon, both with
$f$
-vector
$(6, 10, 6)$
. -
(ii) For $d=4$
, the minimizers with seven vertices are the pyramid over
$T\hskip -1.6pt A(3)$
and the
$2$
-fold pyramid over a pentagon, both with
$f$
-vector
$(7,16,16,7)$
. -
(iii) The minimizers with eight vertices, all with $f$
-vector
$(8,18,17,7)$
, are the polytopes
$T\hskip -1.6pt A(4)$
,
$P\hskip -1.6pt m(3,1)$
,
$W\hskip -1.6pt P$
, and
$\operatorname {\mathrm {pyr}}(\Sigma (3))$
.
Proof The catalogs of 3-polytopes with six vertices (see, for instance, [Reference Britton and Dunitz2, Figure 3]) reveal that the two possible minimizers are
$T\hskip -1.6pt A(3)$
and the pyramid over the pentagon; both have
$f$
-vector
$(6, 10, 6)$
. This can be deduced easily from Steinitz’s theorem.
The 4-polytopes with exactly seven vertices were completely characterized by Grünbaum, in terms of their Gale diagrams: a complete list, together with the corresponding
$f$
-vectors, can be found in [Reference Grünbaum4, Figure 5]. The minimizers with seven vertices are the pyramid over
$T\hskip -1.6pt A(3)$
and the 2-fold pyramid over a pentagon, with
$f$
-vector (7,16,16,7). Every other 4-polytope with seven vertices and at least seven facets has
$f_1\geqslant 17$
and
$f_2\geqslant 17$
.
A 4-polytope with 8 vertices and 16 edges must be a prism, which has
$d+2$
facets. There is no 4-polytope with 8 vertices and 17 edges [Reference Grünbaum5, Section 10.4]. There are exactly four 4-polytopes with 8 vertices and 18 edges, namely,
$T\hskip -1.6pt A(4)$
,
$P\hskip -1.6pt m(3,1)$
,
$W\hskip -1.6pt P$
, and a pyramid over
$\Sigma (3)$
, all with
$f$
-vector
$(8,18,17,7)$
(see [Reference Pineda-Villavicencio, Ugon and Yost11, Lemma 18]). Any 4-polytope with eight vertices and at least seven facets must satisfy
$f_2=f_1+f_3-f_0\geqslant 18+7-8=17$
, with strict inequality unless
$f_1=18$
and
$f_3=7$
. Thus, these four polytopes are also the only minimizers of
$f_2$
for 4-polytopes with eight vertices and at least seven facets. Any other 4-polytope with eight vertices and at least seven facets has more edges and 2-faces than these examples.
It is worth noting that the
$f$
-vectors of all 4-polytopes with up to nine vertices, together with the corresponding number of combinatorial types, can be found in [Reference Firsching3, Tables 6 and 7].
We recall the smallest simple
$d$
-polytopes (see [Reference Pineda-Villavicencio, Ugon and Yost9, Lemma 2.19]).
Remark 3.5 The smallest vertex counts of simple
$d$
-polytopes are
$d + 1$
(the
$d$
-simplex),
$2d$
(the simplicial
$d$
-prism), and
$3d-3$
(the polytope
$T(2)\times T(d-2)$
). These all have
$d+2$
facets.
Theorem 3.6 Let
$d\geqslant 3$
and
$3 \leqslant s \leqslant d$
, and let
$P$
be a
$d$
-polytope with
$d+s$
vertices and at least
$d+3$
facets. Then
$f_k(P) \geqslant \zeta _k(d+s,d)$
for each
$k\in [1, d-2]$
.
Proof Proceed by induction on
$d\geqslant 3$
for all
$3 \leqslant s \leqslant d$
. The cases
$d=3,4$
are covered in Proposition 3.4, so we assume that
$d\geqslant 5$
. Remark 3.5 gives that
$P$
is not simple. Let
$v$
be a nonsimple vertex of
$P$
with maximum degree and let
$F$
be a facet of
$P$
that does not contain
$v$
and has the maximum number
$d+m$
of vertices where
$0\leqslant m\leqslant d-1$
.
Case 1
$f_{0}(F)=f_{0}(P)-1$
; that is,
$m=s-1$
.
The induction hypothesis on
$d-1$
for
$3\leqslant s \leqslant d-1$
yields that
If
$s=d,$
then
$F$
has
$2d-1=2(d-1)+1$
vertices and at least
$(d-1)+3$
facets. In this case, Theorem 2.4 gives that
$f_{k}(F)\geqslant f_{k}(P\hskip -1.6pt m(d-1))$
. This combined with the relation
$f_{k}(P)=f_{k}(F)+f_{k-1}(F)$
yields the result.
Case 2
$f_0(F)=d+m=d-1+m+1$
, where
$ m\in [2, s-2]$
.
Subcase 2.1 The facet F has at least d+2=(d-1)+3 facets.
Since
$\deg _{P}(v)\geqslant d+1$
, by Proposition 3.3, the number of
$k$
-faces containing at least one of the vertices outside
$F$
is at least
$ \phi _{k-1}(d+1, d-1)+ \sum _{i=2}^{s-m} \binom {d-i+1}{k}$
. The induction hypothesis on
$d-1$
yields that
The last inequality holds with equality if and only if
$m=s-2$
.
Subcase 2.2 The facet F has
$d+1=(d-1)+2$
facets and is not a simple polytope.
If
$F$
is not a simple
$(d-1)$
-polytope, which occurs when either
$f_0(F)\leqslant 2d-3$
or
$f_{0}(F)=2d-2$
and
$F$
is not a simplicial
$(d-1)$
-prism (Remark 3.5), then, by Lemma 2.1,
$F$
must be a pyramid whose apex has degree at least
$f_0(F)=d+m$
in
$P$
. Thus,
$\deg _{P}(v)\geqslant d+m=d-1+m+1$
.
By Proposition 3.3, the number of
$k$
-faces containing at least one of the vertices outside
$F$
is at least
$ \phi _{k-1}(d+m, d-1)+\sum _{i=2}^{s-m}\binom {d-i+1}{k}$
. Furthermore,
${f_k(F)\geqslant \phi _{k}(d+m, d-1)}$
by Theorem 1.1. Hence, we have that
As in the previous scenario, the last inequality holds with equality if and only if
$m=s-2$
.
Remark 3.7 (Number of facets containing the vertex
$v$
)
In case of equality, the vertex
$v$
can have degree either
$d+s-2$
or
$d+s-1$
in
$P$
. Additionally, the number of
$k-1$
faces in the vertex figure of
$v$
must equal
$\phi _{k-1}(d+s-2,d-1)$
.
-
(i) If its degree is $d+s-2$
, then its vertex figure must be an
$(s-1,d-s)$
-triplex, implying that
$v$
is contained in exactly
$d+1$
facets of
$P$
. -
(ii) If the degree of $v$
is
$d+s-1$
and
$s<d$
, since $$ \begin{align*} \phi_{k-1}(d+s-2,d-1)\leqslant \phi_{k-1}(d+s-1,d-1)\leqslant f_{k-1}(P/v), \end{align*} $$
then Theorem 1.1 gives that $P/v$
is an
$(s,d-1-s)$
-triplex, implying that
$v$
is contained in exactly
$d+1$
facets of
$P$
. From
$\phi _{k-1}(d+s-1,d-1)=\phi _{k-1}(d+s-2,d-1)$
, which amounts to
$\binom {d-s}{k}=\binom {d-s+1}{k}$
, it follows that
$\binom {d-s}{k-1}=0$
. Hence, the equality in this case happens provided that
$k\geqslant d-s+2$
. -
(iii) Suppose that the degree of $v$
is
$d+s-1$
and
$s=d$
. If
$f_{d-2}(P/v)\geqslant d+2$
, then Theorem 2.4 gives that
$f_{k-1}(P/v)\geqslant \binom {d}{k}+2\binom {d-1}{k}-\binom {d-2}{k}>\phi _{k-1}(2d-2,d-1)$
. If
$f_{d-2}(P/v_1)=d+1$
, then Theorem 2.4 gives that
$f_{k-1}(P/v)\geqslant f_{k-1}((T^{d-1,d-1-(\lfloor {(d-1)/2}\rfloor +2)}_{2})^*)>\phi _{k-1}(2d-2,d-1)$
. Thus, equality does not arise in this case.
Subcase 2.3 The facet F has
$d+1=(d-1)+2$
facets and is a simple polytope.
This implies that
$F$
has
$2d-2$
vertices and is a simplicial
$(d-1)$
-prism. Label the vertices in a simplex
$(d-2)$
-face
$R$
of
$F$
as
$w_1 ,\dots , w_{d-1}$
and the vertices in the other simplex
$(d-2)$
-face
$R'$
of
$F$
as
$w^{\prime }_1 ,\dots , w_{d-1}'$
. Then
$R\cap R'= \emptyset $
. Additionally, label the two vertices outside
$F$
as
$v, v'$
. Since
$v$
has degree at least
$d+1$
in
$P$
, there are at least
$2d-1$
edges between
$\{v,v'\}$
and
$F$
. Thus, there is a vertex in
$F$
, say
$w_1'$
, that is adjacent to both
$v$
and
$ v'$
(see Figure 2).
$F$
is a prism.
Consider the other facet
$F_1$
that intersects
$F$
at the simplicial
$(d-2)$
-prism
$K_1=\operatorname {\mathrm {conv}}\{w_i, w_i': i=2,\dots , d-1\}$
. It follows that
$f_{0}(F_1)=2d-3$
or
$2d-2$
.
First suppose that
$f_{0}(F_{1})=2d-3$
. Then
$F_1$
is a pyramid over
$K_1$
and thus, has
$d+1 (d-2)$
-faces. The apex of
$F_1$
, namely,
$v$
or
$v'$
, has degree at least
$2d-2$
in
$P$
as it is adjacent to
$w_1'$
.
The computation in (3.3) also applies here:
In case of equality in (3.4), we find that
$v'$
cannot be the apex of
$F_1$
, as
$v'$
is present in exactly
$\binom {d-1}{k} \; k$
-faces not containing
$v$
. (We can actually apply Equation (3.3), then in case of equality, it implies that
$v'$
has to be simple in every facet not containing
$v$
, so
$v'$
cannot be the apex of
$F_1$
.) Furthermore, by reasoning as in Remark 3.7(iii), since
$f_{k-1}(P/v)=\phi _{k-1}(2d-2,d-1)$
, we find that
$P/v$
must have
$d+1 \; (d-2)$
-faces and be a simplicial
$(d-1)$
-polytope. In particular, the vertex
$v$
has degree exactly
$2d-2$
.
Suppose that
$F_1$
has
$2d-2$
vertices. Then
$F_{1}$
is not a pyramid. If
$F_1$
has at least
$d+2$
facets, then, since
$w_{1}'$
is a nonsimple vertex outside
$F_1$
, we settle this by the calculation of Equation (3.2). We can then assume that
$F_1$
has
$d+1$
facets, in which case
$F_1$
is a simplicial
$(d-1)$
-prism (see Lemma 2.1). Without loss of generality, we may assume that, within
$F_1$
, the vertex
$v$
is adjacent to
$w_2,\dots , w_{d-1}$
and
$v'$
is adjacent to
$w_2',\dots , w_{d-1}'$
. It follows that
$w_2,\dots , w_{d-1}$
,
$w_2',\dots , w_{d-1}'$
are simple vertices in
$P$
.
As
$F_1$
is a prism, the lines containing the edges
$[w_i, w_i']$
,
$i=2,\dots ,d-1$
and the line containing the edge
$[v, v']$
have the property that every two of them are coplanar. Likewise, since
$F$
is a prism, every two of the lines containing the edges
$[w_i, w_i']$
,
$i=1,\dots , d-1$
, are coplanar. It follows that
$[w_1, w_1']$
is coplanar with
$[v, v']$
. Since the vertex
$w_1'$
is adjacent to both
$v$
and
$v'$
, while the vertex
$w_1$
is adjacent to either
$v$
or
$v'$
, we have a violation of convexity. Therefore this case does not arise.
Case 3 The facet
$F$
has
$d+1$
vertices.
There are
$s-1$
vertices outside
$F$
, say
$\{u_{1},\ldots ,u_{s-1}\},$
where
$u_{1}=v$
. By Proposition 3.3, there is a sequence
$F_1, \ldots , F_{s-1}$
of faces of
$P$
such that each
$F_i$
has dimension
$d-i+1$
and contains
$u_i$
, but does not contain any
$u_j$
with
$j<i$
. The number of
$k$
-faces in
$P$
is bounded from below as follows:
This settles this case.
Case 4 The facet
$F$
(and any other facet not containing
$v$
) is a simplex.
Let
$v_{1}$
be a vertex not in
$F$
other than
$v$
. By assumption, there must be a simplex facet
$F'$
containing
$v_{1}$
but not
$v$
. Let
$v_{1},\ldots ,v_{a}$
represent the vertices in
$F'\setminus F$
and
$v_{a+1},\ldots ,v_{s}$
the vertices outside
$F\cup F'$
. We consider two scenarios according to the number
$s-a$
of vertices outside
$F \cup F'$
.
Subcase 4.1 The inequality
$s-a \geqslant 2$
holds.
By Proposition 3.3, there is a sequence
$J_1,\ldots , J_{a}$
of faces in
$F'$
such that each
$J_i$
has dimension
$d-1-i+1$
and contains
$v_i$
but does not contain
$v_j$
with
$j<i$
. Additionally, there is a sequence
$F_{a+1},\ldots , F_{s}$
of faces in
$P$
such that each
$F_{\ell }$
has dimension
$d-\ell +(a+1)$
. Consequently, we have the following:
This subcase is now settled.
Subcase 4.2 The equality
$s-a=1$
holds; that is, v is the only vertex that is outside
$F \cup F'$
.
In this case,
$\# (F \cap F') \geqslant 1$
, and each vertex in
$F \cap F'$
is adjacent to every other vertex in
$F \cup F'$
, thereby implying that such a vertex has degree at least
$d+s-2=\# (F \cup F')$
in
$P$
. By maximality,
$\deg (v)\geqslant d+s-2$
. Again, by Proposition 3.3, the number of
$k$
-faces containing a vertex outside
$F$
is at least
$\sum _{i=2}^{s}\binom {d-i+1}{k}+\phi _{k-1}(d+s-2, d-1)$
. Hence, we have the following:
This subcase is also settled.
We delve deeper into the degree of
$v$
and the facets containing it.
Remark 3.8 In case of equality in (3.6), we have the following:
(i) If
$s\leqslant d-1,$
then
$\# (F\cap F')\geqslant 2$
. Since
$v$
has degree at least
$d+s-2$
, it must be adjacent to a vertex
$w \in F\cap F'$
, as there are not
$d+s-2$
vertices outside the intersection. Consequently, the vertex
$w$
has degree
$d+s-1$
in
$P$
, which implies that
$v$
has degree
$d+s-1$
in
$P$
.
(ii) Suppose that
$s=d$
. If
$\deg (v)= 2d-1$
, then the vertex figure
$P/v$
has
$2d-1$
vertices. Reasoning as in Remark 3.7(iii), we see that this case does not arise.
Assume that
$\deg (v)= 2d-2$
. There is a facet that contains
$v$
and has
$2d-2$
vertices in total. Indeed, let
$w$
be the unique vertex in
$F\cap F'$
. Then we get that
$\deg (w)=2d-2$
and that
$w$
is not adjacent to
$v$
(otherwise
$\deg (w)=2d-1$
). Furthermore, since
$f_{k}(P/v)=\phi _{k}(2d-2,d-1)$
, we find that
$P/v$
is a simplicial
$(d-1)$
-prism. Consider a simplicial
$(d-2)$
-prism
$R$
in
$P/v$
. The facet
$J$
of
$P$
containing
$v$
(and
$R$
) has at least
$2(d-2)+1$
vertices. It follows that
$J$
must also contain
$w$
; otherwise,
$J$
is a nonsimplex facet missing a vertex of largest degree. That is,
$f_{0}(J)=2d-2$
.
In every scenario of the remark,
$v$
is contained in exactly
$d+1$
facets of
$P$
.
The proof of the theorem is complete.
3.1 Equality analysis
Theorems 3.2 and 3.6 deal with the inequality part of our main theorem (Theorem 3.1). We now characterize the equality cases.
Remark 3.9 For the parameters
$(d,s,m),$
where
$d\geqslant 5$
,
$3\leqslant s\leqslant d$
and
$0\leqslant m\leqslant s-1$
, let
$P$
be a
$d$
-polytope with
$d+s$
vertices and at least
$d+3$
facets, let
$v$
be a nonsimple vertex with the largest degree in
$P$
, let
$F$
be a facet not containing
$v$
and with the largest possible number
$d+m$
of vertices (subject to not containing
$v$
), and let
$X$
be the set of vertices outside
$F$
. The proof of Theorem 3.6 establishes strict inequality if
$2\leqslant m\leqslant s-3$
. The possible equality cases can occur only in the following settings:
-
(i) $\mathbf {m=s-1}$
(Theorem 3.6, Case 1): The facet
$F$
satisfies
$f_k(F)=f_{k}(P\hskip -1.6pt m(s-1,d-s))=\zeta _k(d+s-1, d-1)$
for each
$k\in [1, d-2]$
(see (3.1)). If
$s=d$
, then
$f_k(F)=f_k(P\hskip -1.6pt m(d-1))$
for each
$k\in [1, d-2]$
. -
(ii) $\mathbf {m=s-2}$
(Theorem 3.6, Subcase 2.1): The facet
$F$
has at least
$d+2 (d-2)$
-faces and satisfies
$f_k(F)=f_{k}(P\hskip -1.6pt m(s-2,d-s+1))=\zeta _k(d+s-2, d-1)$
for
$k\in [1, d-2]$
. Additionally, the vertex
$v$
has degree
$d+1$
and its vertex figure is a
$(2,d-3)$
-triplex. The number of
$k$
-faces containing the other vertex in
$X\setminus \{v\}$
but not
$v$
is
$\sum _{i=2}^{2}\binom {d-i+1}{k}=\binom {d-1}{k}$
(see (3.2)). -
(iii) $\mathbf {m=s-2}$
(Theorem 3.6, Subcase 2.2): The facet
$F$
has
$d+1 \; (d-2)$
-faces and is an
$(s-1,d-s)$
-triplex. The vertex
$v$
has degree
$d+s-2$
and its vertex figure is an
$(s-1,d-s)$
-triplex. Additionally, the number of
$k$
-faces containing the other vertex in
$X\setminus \{v\}$
but not
$v$
is
$\sum _{i=2}^{2}\binom {d-i+1}{k}=\binom {d-1}{k}$
(see (3.3)). -
(iv) $\mathbf {m=s-2}$
(Theorem 3.6, Subcase 2.2): The facet
$F$
has
$d+1 \;(d-2)$
-faces and is an
$(s-1,d-s)$
-triplex. The vertex
$v$
has degree
$d+s-1$
and its vertex figure is an
$(s,d-1-s)$
-triplex with
$s\leqslant d-1$
. Furthermore,
$\phi _{k-1}(d+s-1,d-1)=\phi _{k-1}(d+s-2,d-1)$
, which implies that
$\binom {d-s}{k}=\binom {d-s+1}{k}$
or, equivalently, that
$k\geqslant d-s+2$
(see Remark 3.7(ii)). Additionally, the number of
$k$
-faces containing the other vertex in
$X\setminus \{v\}$
but not
$v$
is
$\sum _{i=2}^{2}\binom {d-i+1}{k}=\binom {d-1}{k}$
(see (3.3)). -
(v) $\mathbf {m=d-2}$
(Theorem 3.6, Subcase 2.3): The facet
$F$
is a simplicial
$(d-1)$
-prism, there is a facet
$F'$
which is a pyramid over a simplicial
$(d-2)$
-prism from
$F$
and whose apex is
$v$
. The degree of
$v$
in
$P$
is exactly
$2d-2$
and its vertex figure is a simplicial
$(d-1)$
-prism. Additionally, the number of
$k$
-faces containing the vertex in
$X\setminus \{v\}$
but not
$v$
is
$\binom {d-1}{k}$
(see (3.4)). -
(vi) $\mathbf {m=1}$
(Theorem 3.6, Case 3): The facet
$F$
is a
$(2,d-3)$
-triplex. The vertex
$v$
has degree
$d+1$
and its vertex figure is a
$(2,d-3)$
-triplex, and the number of
$k$
-faces containing some vertex in
$X\setminus \{v\}$
but not
$v$
is
$\sum _{i=2}^{s-1}\binom {d-i+1}{k}$
(see (3.5)). -
(vii) $\mathbf {m=0}$
(Theorem 3.6, Subcase 4.2): Every facet not containing a nonsimple vertex with the largest degree is a simplex. Moreover, there is a simplex facet
$F'$
such that
$F\cup F'$
contains
$d+s-1$
vertices. If
$s\leqslant d-1$
, then the vertex
$v$
has degree
$d+s-1$
and its vertex figure is an
$(s,d-1-s)$
-triplex. If
$s= d$
, then the vertex
$v$
has degree
$2d-2$
and its vertex figure is a simplicial
$(d-1)$
-prism. Additionally, the number of
$k$
-faces containing some vertex in
$X\setminus \{v\}$
but not
$v$
is
$\sum _{i=2}^{s}\binom {d-i+1}{k}$
(see (3.6) and Remark 3.8).
Lemma 3.10 Let
$d\geqslant 5$
and
$3\leqslant s\leqslant d$
be given parameters, and let
$P$
be a nonpyramidal
$d$
-polytope with
$d+s$
vertices and at least
$d+3$
facets. If
$f_k(P)=\zeta _k(d+s,d)$
for some
$k\in [1, d-2]$
, then
$P$
has exactly
$d+3$
facets.
Proof We are inspired by the reasoning in [Reference Xue14, Section 4]. The scenarios where we get equality in the proof of Theorem 3.6 are listed in Remark 3.9. In every case, the following hold:
-
(i) There is a nonsimple vertex $v_1$
(with the maximum degree) contained in exactly
$d+1$
facets. -
(ii) There is a facet $J$
with
$d+m$
vertices not containing
$v_1$
where
$0\leqslant m\leqslant s-2$
. -
(iii) Let $Y:=\{v_1,\ldots ,v_{s-m}\}$
be the set of vertices outside
$J$
. The vertices outside
$J$
other than
$v_1$
are contained in exactly
$\binom {d-1}{k}\ k$
-faces of
$P$
.
In Remark 3.9, the vertex
$v_1$
is the vertex
$v$
,
$Y=X$
, and
$J=F$
.
Claim 1 The number of
$k$
-faces in
$P$
containing the vertex
$v_i$
and not
$v_j$
with
$i\geqslant 2$
and
$j<i$
is precisely
$\binom {d-i+1}{k}$
.
Proof of claim
The minimum number of
$k$
-faces within a
$(d-i+1)$
-face that contains the vertex
$v_{i}$
is attained when the vertex figure is a simplex, namely, a
$(d-i)$
-simplex. Since the number of
$k$
-faces in
$P$
containing some vertex in
$Y\setminus \{v_1\}$
is precisely
$\sum _{i=2}^{s-m}\binom {d-i+1}{k}$
, each vertex figure must be a minimizer.
The facets of
$P$
can be partitioned into the facet
$J$
and the sets
$X_i$
of facets containing the vertex
$v_i$
but no vertex
$v_j$
with
$j<i$
. From the first paragraph, we get that
$\# X_1=d+1$
. We prove that
$\# X_2=1$
and
$\# X_{\ell }=0$
for
$\ell \in [3, s-m]$
.
Suppose that there are two facets
$J_2$
and
$J_2'$
in
$X_{2}$
. Then there must exist a
$k$
-face
$R$
of
$J_{2}'$
that is not a face of
$J_{2}$
. Since there are already
$\binom {d-1}{k}\ k$
-faces in
$J_{2}$
containing
$v_{2}$
(and not
$v_{1}$
), the number of
$k$
-faces in
$P$
containing
$v_{2}$
but not
$v_{1}$
is greater than
$\binom {d-1}{k}$
, contradicting Claim 1. Thus,
$\# X_{2}=1$
.
The same idea proves that
$\# X_{3}=0$
. If there were a facet
$J_{3}$
containing
$ v_{3}$
but not
$v_{1}$
or
$v_{2}$
, then the number of
$k$
-faces in
$P$
containing
$ v_{3}$
but not
$ v_{1}$
or
$ v_{2}$
would be at least the number of
$k$
-faces in
$J_{3}$
containing
$v_{3}$
, namely,
$\binom {d-1}{k}$
, which again contradicts Claim 1. Since we have the freedom to choose a different ordering of the vertices in
$Y\setminus \{v_1\}$
, any vertex in
$Y\setminus \{v_{1},v_{2}\}$
can be picked as
$v_{3}$
. Thus,
$\# X_{\ell }=0$
for
$\ell \in [3, r]$
, yielding that
$P$
has
$d+3$
facets.
We write down a corollary of Lemma 3.10 to aid our future discussion.
Corollary 3.11 Let
$d\geqslant 5$
and
$3\leqslant s\leqslant d$
, let
$P$
be a
$d$
-polytope with
$d+s$
vertices and at least
$d+3$
facets, let
$v$
be a nonsimple vertex with the maximum degree, and let
$F$
be a facet not containing
$v$
and with a largest possible number of vertices. In the equality condition of Subcases 2.2 and 2.3 of Theorem 3.6, the facet
$F$
has
$d+s-2$
vertices and
$d+1 \; (d-2)$
-faces. Moreover, for the vertex
$v'\ne v$
outside
$F$
, the following hold:
-
(i) There is a unique facet containing both $v$
and
$v'$
, which intersects
$F$
at a
$(d-3)$
-face. -
(ii) There is a unique facet containing $v'$
but not
$v$
, which intersects
$F$
at a
$(d-2)$
-face. -
(iii) There are either $d-2$
or
$d-1$
facets containing both
$v$
and
$v'$
that intersect with
$F$
at a
$(d-2)$
-face.
Proof In the notation of Lemma 3.10, we assume that the facet
$F$
here is the facet
$J$
there, the vertex
$v$
is the vertex
$v_{1}$
there, and the vertex
$v'$
is the vertex
$v_{2}$
there.
(i) Since
$F$
contains exactly
$d+1\; (d-2)$
-faces and, by Lemma 3.10,
$P$
contains exactly
$d+3 \;(d-1)$
-faces, there must exist a unique facet in
$P$
consisting of the convex hull of a
$(d-3)$
-face of
$F$
and the vertices
$v$
and
$v'$
.
(ii) The proof of Claim 1 in Lemma 3.10 shows that the set
$X_{2}$
of facets containing
$v'$
but not
$v$
has cardinality one.
(iii) Parts (i) and (ii) count two facets in
$P$
containing
$v'$
. The remaining facets containing
$v'$
must also contain
$v$
and a
$(d-2)$
-face of
$F$
. If
$v'$
is simple in
$P$
, there are
$d-2$
such facets; otherwise, there are
$d-1$
.
Theorem 3.12 (Equality)
Let
$d\geqslant s\geqslant 3$
be parameters and let
$P$
be a
$d$
-polytope with
$d+s$
vertices and at least
$d+3$
facets. If, for some
$k\in [1, d-2]$
,
then the following statements hold:
-
(i) If $s=3$
, then
$P$
is either the
$(d-2)$
-fold pyramid over a pentagon or the
$(d-3)$
-fold pyramid over
$T\hskip -1.6pt A(3)$
. -
(ii) If $5\leqslant s\leqslant {d-1}$
and
$k\leqslant d-s+1$
, then
$P$
is either the
$(d-s+1)$
-fold pyramid over an
$(s-1)$
-pentasm or the
$(d-s)$
-fold pyramid over
$T\hskip -1.6pt A(s)$
. -
(iii) If $5\leqslant s\leqslant {d-1}$
and
$d-s+2\leqslant k\leqslant d-2$
, then
$P$
is either the
$(d-s+1)$
-fold pyramid over an
$(s-1)$
-pentasm, the
$(d-s)$
-fold pyramid over
$T\hskip -1.6pt A(s)$
, or the
$(d-s-1)$
-fold pyramid over
$Z(s+1)$
. -
(iv) If $s=4$
and either
$k\leqslant { d-3}$
or
$d=4$
and
$k=2$
, then
$P$
is either the
$(d-3)$
-fold pyramid over a
$3$
-pentasm, the
$(d-3)$
-fold pyramid over
$\Sigma (3)$
, the
$(d-4)$
-fold pyramid over
$T\hskip -1.6pt A(4)$
, or the
$(d-4)$
-fold pyramid over
$W\hskip -1.6pt P$
. -
(v) If $s=4$
,
$k=d-2,$
and
$d\geqslant 5$
, then
$P$
is either the
$(d-3)$
-fold pyramid over a
$3$
-pentasm, the
$(d-3)$
-fold pyramid over
$\Sigma (3)$
, the
$(d-4)$
-fold pyramid over
$T\hskip -1.6pt A(4)$
, the
$(d-4)$
-fold pyramid over
$W\hskip -1.6pt P,$
or the
$(d-5)$
-fold pyramid over
$Z(5)$
. -
(vi) If $s=d$
and
$d\geqslant 5$
, then
$P$
is either
$T\hskip -1.6pt A(d)$
or the pyramid over a
$(d-1)$
-pentasm.
Proof We proceed by induction on the dimension. The induction base is
$d=3$
and 4, which is covered by Proposition 3.4.
Let
$P$
be a
$d$
-polytope as in the hypothesis. Suppose now the theorem holds for dimensions
$3, 4, \dots , d-1$
. As before, let
$v$
be a nonsimple vertex of
$P$
with maximum degree and let
$F$
be a facet of
$P$
that does not contain
$v$
and has a maximum number
$d+m$
of vertices (among such facets). We consider each of the scenarios listed in Remark 3.9.
Remark 3.9(i) The facet
$F$
has
$d+s-1$
vertices. If
$s \leqslant d-1$
, by induction on
$d-1$
, the facet is one of the minimizers. Thus,
$P$
is a pyramid over
$F$
and has the desired form. If
$s=d$
, by Theorem 3.6, Case 1 (and [Reference Pineda-Villavicencio and Yost13]), the facet
$F$
is a
$(d-1)$
-pentasm. Hence,
$P$
is a pyramid over the pentasm; that is, a
$P\hskip -1.6pt m(d-1, 1)$
.
We now consider the scenarios in Remark 3.9(ii)–(v). Here, the facet
$F$
has
$d+s-2$
vertices with
$s\geqslant 4$
. (If
$s=3,$
then
$F$
has
$d+1$
vertices, a scenario considered in Remark 3.9(vi)). Denote by
$v'$
the vertex other than
$v$
and outside
$F$
. In Remark 3.9(ii)–(v), note that the vertex
$v'$
is simple in the unique facet that contains it but does not contain
$v$
.
Remark 3.9(ii) The facet
$F$
has at least
$d+2 \; (d-2)$
-faces and satisfies
$f_{k}(F)=\zeta _k(d+s-2, d-1)$
. By the induction hypothesis,
$F$
is either
$P\hskip -1.6pt m(s-2, d-s+1)$
,
$T\hskip -1.6pt A(s-1, d-s)$
,
$Z(s, d-s-1)$
,
$\operatorname {\mathrm {pyr}}_{d-5}(W\hskip -1.6pt P)$
, or
$\operatorname {\mathrm {pyr}}_{d-4}(\Sigma (3))$
.
First suppose that
$F$
is not a pyramid. For
$d\geqslant 5$
, this means that the facet
$F$
could be only
$T\hskip -1.6pt A(d-1)$
,
$Z(d-1)$
, or
$W\hskip -1.6pt P$
. Remarks 2.6 and 2.7 assert that
$T\hskip -1.6pt A(d-1)$
and
$Z(d-1)$
both have a vertex with degree
$2d-4$
, which results in a degree at least
$2d-3$
in
$P$
. Since the vertex
$v$
has degree
$d+1$
, so does every nonsimple vertex in
$P$
. Thus, we find that
$d\leqslant 4$
, which has been already covered.
It remains to consider the scenario where
$F$
is
$W\hskip -1.6pt P$
. We denote by
$v_1, v_2, v_3, v_4$
the four nonsimple vertices of
$F$
(see Figure 1(b)). Since
$v'$
is simple in the unique facet containing it but not
$v$
, this facet must be the simplex with vertices
$v',v_{1},v_{2},v_{3},v_{4}$
. Additionally, because the degree of
$v$
is six, every nonsimple vertex in
$P$
must have degree six. Thus, the vertices
$v_{1},v_{2},v_{3},v_{4}$
each have exactly one neighbor outside
$F$
, which is
$v'$
. As a consequence, the neighbors of
$v$
in
$P$
other than
$v'$
must be the four vertices in
$F$
other than
$v_{1},v_{2},v_{3},v_{4}$
, ensuring that the degree of
$v$
in
$P$
is five, a contradiction.
Assume that
$F$
is a pyramid. Since
$f_{0}(F)\geqslant d+2$
, its apex has at least
$d+1$
neighbors in
$F$
and, therefore has degree at least
$d+2$
in
$P$
, contradicting the degree of
$v$
.
Remark 3.9(iii) The facet
$F$
has
$d+1 (d-2)$
-faces and is an
$(s-1, d-s)$
-triplex. Then
$d-s\geqslant 1$
. Moreover, the vertex
$v$
has degree
$d+s-2$
.
Suppose that
$d-s \geqslant 2$
. There are at least two apices
$x_1$
and
$x_{2}$
in
$F$
. For
$i=1,2$
, consider the other facet
$F_i$
in
$P$
intersecting
$F$
at a
$(d-2)$
-face that does not contain
$x_i$
. Since
$P$
is not a pyramid, each
$F_i$
must be pyramid with apex either
$v$
or
$v'$
(but not both). Since
$s\geqslant 4$
, each facet
$F_i$
is not a simplex. Therefore, as
$v'$
is simple in each of the facets containing it, for each
$i=1,2$
,
$v'\not \in F_{i}$
. Thus,
$v\in F_i$
for each
$i=1,2$
. It follows that
$v$
is adjacent to every other vertex in the polytope; that is, the degree of
$v$
is
$d+s-1$
, contradicting our assumption.
Assume that
$d-s=1$
. Then the facet
$F$
is a pyramid over a simplicial
$(d-2)$
-prism
$R$
. Then
$R$
is the convex hull of two
$(d-3)$
-simplices
$K$
and
$K'$
. Denote by
$x$
the apex of
$F$
.
Consider a facet
$F'$
in
$P$
containing
$R$
but not
$x$
. The facet
$F'$
is a pyramid with apex either
$v$
or
$v'$
; otherwise,
$f_0(F')=d+s-1$
and
$P$
would be a pyramid whose apex
$x$
has degree
$2d-2$
, which is larger than the degree of
$v$
, contradicting our assumption. It follows that
$v \in F'$
, as
$v'$
is simple in each facet that contains it but does not contain
$v$
. Because
$\deg _{P}(v)=2d-3$
,
$v$
cannot be adjacent to
$x$
.
It is true that
$\deg _{P}(v') <\deg _{P}(v)$
; otherwise, we could pick
$v'\notin F$
as our nonsimple vertex with the maximum degree. Additionally,
$v$
would need to be simple in the facet that contains it but does not contain
$v'$
. However,
$v$
is not simple in
$F'$
.
Consider a facet
$J'$
in
$P$
containing
$v'$
but not
$v$
. Then
$J'$
must be a pyramid with apex
$v'$
and intersecting
$F$
at a ridge. Since
$v'$
is simple in
$J'$
, the facet
$J'$
must be a simplex. Without loss of generality, we may assume that
$J'=\operatorname {\mathrm {conv}}(\{ v',x\}\cup K')$
. Since
$\deg (v') < \deg (v)=2d-3$
, we find that
$v'$
is not adjacent to at least two vertices in
$K$
. Finally, we consider another facet
$J$
in
$P$
containing the
$(d-2)$
-simplex
$\operatorname {\mathrm {conv}} \{ x\}\cup K$
. Since
$v'$
is not adjacent to two vertices in
$K$
, the degree of
$v'$
in
$J$
would be at most
$d-2$
, a contradiction. Thus,
$v'\notin J$
and, therefore
$v\in J$
. On the other hand, because
$v$
is not adjacent to
$x$
, the vertex
$v\notin J$
, a contradiction.
Remark 3.9(iv) The facet
$F$
has
$d+1\; (d-2)$
-faces and is an
$(s-1, d-s)$
-triplex. Denote by
$x_1,\ldots , x_{d-s}$
the apices in
$F$
, where
$d-s\geqslant 1$
. Moreover, the vertex
$v$
has degree
$d+s-1$
.
For
$i=1,\ldots , d-s$
, consider the facet
$F_{i}$
in
$P$
intersecting
$F$
at the
$(d-2)$
-face of
$F$
not containing
$x_{i}$
. If
$F_{i}$
contained both
$v$
and
$v'$
, then the polytope would be a pyramid, a case already covered. Thus,
$F_{i}$
is a pyramid with apex either
$v$
or
$v'$
. Since
$f_{0}(F_{i})\geqslant d+2$
, and
$v'$
is simple in any facet that contains it but does not contain
$v$
, the latter is impossible. So the apex of
$F_{i}$
is
$v$
. It follows that, for each
$i=1,\ldots , d-s$
,
$F_{i}$
contains
$v$
but not
$v'$
. Additionally, consider a facet
$J'$
in
$P$
containing
$v'$
but not
$v$
. Then
$J'$
must be a pyramid with apex
$v'$
and intersecting
$F$
at a ridge. Since
$v'$
is simple in
$J'$
, any such facet
$J'$
must be a simplex.
Suppose that
$d-s \geqslant 3$
. Since
$F$
does not contain
$v'$
, there are at least four facets in
$P$
not containing
$v'$
. However, by Lemma 3.10, the polytope has exactly
$d+3$
facets, leaving at most
$d-1$
facets containing
$v'$
, which is not possible.
Suppose
$d-s=2$
. Then
$F$
is a two-fold pyramid over a simplicial
$(d-3)$
-prism
$R$
. Then
$R$
is the convex hull of two
$(d-4)$
-simplices
$K$
and
$K'$
. Without loss of generality, we assume that
$J'=\operatorname {\mathrm {conv}}(\{v',x_{1},x_{2}\}\cup K)$
. By Lemma 3.10, the polytope has exactly
$d+3$
facets. The vertex
$v'$
is not present in precisely three of those facets, namely,
$F_{1}$
,
$F_{2}$
, and
$F$
. Thus,
$v'$
is simple in
$P$
, and so is not adjacent to any of the vertices in
$K'$
. For
$i=1,2$
, there is a facet
$S_i$
in
$P$
containing
$v'$
but not
$x_i$
. Since
$v'$
is simple in
$P$
, each
$S_{i}$
must intersect
$F$
at a
$(d-3)$
-face that contains
$K$
and the other apex, and so must contain
$v$
. This violates Corollary 3.11(i).
Assume that
$d-s=1$
. Then
$F$
is a pyramid over a simplicial
$(d-2)$
-prism
$R$
, and so
$f_{0}(F)=2d-3$
. The face
$R$
is the convex hull of two
$(d-3)$
-simplices
$K:=\operatorname {\mathrm {conv}}\{u_{1},\ldots ,u_{d-2}\}$
and
$K':=\operatorname {\mathrm {conv}}\{u^{\prime }_{1},\ldots ,u^{\prime }_{d-2}\}$
so that the vertices
$u_{i}$
and
$u_{i}'$
are adjacent. Without loss of generality, we assume that
$J'=\operatorname {\mathrm {conv}}(\{v',x_{1}\}\cup K)$
. The facet
$F_{1}$
is a pyramid with apex
$v$
over
$R$
. This means that the vertices in
$K$
have degree exactly
$d+1$
and the vertices in
$K'$
have degree at most
$d+1$
.
For
$i=1,\ldots ,d-2 $
, consider the other facet
$J_{i}$
in
$P$
containing the
$(d-2)$
-face
$I_{i}$
of
$F$
missing the edge
$[u_{i},u_{i}']$
. By Lemma 3.10, the polytope has exactly
$d+3$
facets. The vertex
$v'$
is not present in two of those facets, namely,
$F_{1}$
and
$F$
. As a consequence,
$v'$
needs to be present in at least
$d-3$
of such facets
$J_{i}$
, say in those for
$i\in [1,d-3]$
. Since
$v'$
is simple in the facet that contains it but does not contain
$v$
, the vertex
$v$
must be present in all the facets
$J_{i}$
. Hence,
$f_{0}(J_{i})=f_{0}(F)=2d-3$
, for
$i\in [1, d-3]$
.
For
$i\in [1,d-3]$
, we claim that each facet
$J_{i}$
is neither a pyramid nor a simple polytope, and so, by Lemma 2.1, has at least
$d+2\; (d-2)$
-faces. Indeed, if
$J_{i}$
were a pyramid, then either
$v$
or
$v'$
would be the apex. In case of
$v$
being the apex,
$I_{i}\cup \{v'\}$
would be the base but
$I_{i}$
is already a
$(d-2)$
-face; a similar argument establishes that
$v'$
cannot be the apex of
$J_{i}$
. It is also straightforward that
$J_{i}$
is not a simple polytope.
For each
$i\in [1, d-3]$
, since the vertex
$u_{i}$
(which is outside
$J_{i}$
) has degree
$d+1$
,
$J_{i}$
is a largest facet with at least
$d+2\; (d-2)$
-faces, and
$f_{k}(P)=\zeta _k(d+s,d)$
for some
$k\in [1, d-2]$
, the computation (3.2) in Subcase 2.1 applies and gives that
$f_{k}(J_{i})=\zeta _k(d+s-2,d-1)$
. In this scenario, the induction hypothesis on
$d-1$
ensures that
$J_{i}$
is one of the polytopes in Parts (ii)–(v) of the theorem. Since
$d\geqslant 5$
,
$J_{i}$
is not a pyramid, and
$v$
(and
$x_{1}$
) is adjacent to every other vertex in
$J_{i}$
, the facet
$J_{i}$
can be only
$Z(d-1)$
. According to the structure of
$Z(d-1)$
(Remark 2.7), for
$i\in [1, d-3]$
, the
$d-3$
vertices in
$K$
and
$J_{i}$
have degree
$d$
in
$J_{i}=Z(d-1)$
, so
$v'$
and the
$d-3$
vertices in
$K'$
and
$J_{i}$
must be simple in
$Z(d-1)$
. Since
$d-3\geqslant 2$
, this implies that
$v'$
is not adjacent to any vertex in
$K'$
. This gives the full graph of
$P$
, which consists of the union of the graphs of
$F$
,
$F_{1}$
, and
$J'$
. In particular,
-
• $f_{0}(P)=2d-1$
; -
• the $d-1$
vertices in
$K'\cup \{v'\}$
are simple in
$P$
; -
• the $d-2$
vertices in
$K$
have degree
$d+1$
in
$P$
; -
• the vertices $v$
and
$x_{1}$
have degree
$2d-2$
in
$P$
.
See Figure 1(d) and Remark 2.7.
We now establish the vertex–facet incidence of the polytope. For each
$i\in [1, d-2]$
, let us focus on one
$J_i$
and the other facets that intersect
$J_i$
at a ridge (Remark 2.7). Since
$J_i$
contains exactly
$d+2$
ridges of
$P$
, every other facet of
$P$
intersects
$J_{i}$
at a
$(d-2)$
-face of
$J_{i}$
. Because the degree of
$u_{i}$
in
$P$
is
$d+1$
and that of
$u_{i}'$
is
$d$
, the other facet intersecting
$J_i$
at
$Z(d-2)$
must contain both
$u_i$
and
$ u_i'$
and thus must be one of the facets
$J_{\ell }$
. The
$d-3$
copies of
$Z(d-2)$
in
$J_{i}$
plus
$J_{i}$
result in
$d-2$
facets
$Z(d-1)$
in
$P$
and establish the vertex–facet incidence among them. Similarly, a facet that intersects
$J_i$
at a one of the two copies of
$M(d-3,1)$
in
$J_{i}$
must contain both
$u_i$
and
$u_i'$
. This gives two facets
$M(d-2,1)$
of
$P$
and the vertex–facet incidence among them. There are three simplex
$(d-2)$
-faces in
$J_i$
(Remark 2.7):
Since
$v'$
is simple in
$P$
, one can see that the other facet containing one of such
$(d-2)$
-faces will be, respectively,
The complete vertex–facet incidence of
$P$
is established and so, the polytope is
$Z(d)$
.
Remark 3.9(v) The facet
$F$
is a simplicial
$(d-1)$
-prism and the polytope
$P$
has
$2d$
vertices. Moreover, the vertex
$v$
has degree exactly
$2d-2$
.
Following the proof of Subcase 2.3 of Theorem 3.6, we label the vertices of one
$(d-2)$
-simplex
$R$
of
$F$
by
$w_1 ,\dots , w_{d-1}$
and the vertices of the other
$(d-2)$
-simplex
$R'$
of
$F$
by
$w^{\prime }_1 ,\dots , w_{d-1}'$
, with
$R\cap R'= \emptyset $
. Additionally, let
$v'$
be the vertex outside
$F$
and distinct from
$v$
. Let
$S$
be the facet of
$P$
containing
$v'$
but not
$v$
. Then
$S$
must be a pyramid (with apex
$v'$
) over a
$(d-2)$
-face contained in
$F$
. Since
$v'$
has to be simple in
$S$
, it follows that
$S$
is a simplex and either
$S=\operatorname {\mathrm {conv}}(R'\cup \{v'\})$
or
$S=\operatorname {\mathrm {conv}}(R\cup \{v'\})$
.
Only one vertex of
$P$
is not adjacent to
$v$
, so we can assume without loss of generality that
$w^{\prime }_{1}$
is adjacent to both
$v$
and
$v'$
.
Now consider the other facet
$F_1$
that intersects
$F$
at the simplicial
$(d-2)$
-prism
$K_1=\operatorname {\mathrm {conv}}\{w_i, w_i': i=2,\dots , d-1\}$
. It follows that
$f_{0}(F_1)=2d-3$
or
$2d-2$
.
First suppose that
$f_0(F_1)=2d-3$
. Then the facet
$F_{1}$
is a pyramid with apex
$v$
over the simplicial
$(d-2)$
-prism
$\operatorname {\mathrm {conv}}((R\setminus \{w_{1}\})\cup (R'\setminus \{w^{\prime }_{1}\}))$
of
$F$
. It follows that
$v$
is adjacent to every vertex in
$P$
except for
$w_{1}$
. Thus,
$w_{1}$
is adjacent to
$v'$
.
It follows that
$\deg (v')<2d-2$
. Otherwise,
$v'$
would also be a vertex with maximum degree, so the role of
$v$
and
$v'$
can be swapped. As
$F_1$
is a facet containing
$v$
but not
$v'$
where
$v$
is not simple, we would find a contradiction to the assumption that the unique facet containing
$v'$
and not
$v$
must be simple.
First suppose that
$S=\operatorname {\mathrm {conv}}(R'\cup \{v'\})$
. Since
$\deg _P(v')<2d-2$
, the vertex
$v'$
is not adjacent to at least two vertices from
$w_2, \dots , w_{d-1}$
. Consider the other facet
$J$
of
$P$
that intersects
$F$
at
$R$
. Since
$v'$
is not adjacent to at least two vertices in
$R$
, the vertex
$v'$
would have at most
$d-2$
neighbors in
$J$
, so
$v' \notin J$
. Then, since
$v$
is not adjacent to
$w_1$
, the vertex
$v$
would have at most
$d-2$
neighbors in
$J$
, so
$v \notin J$
. This is absurd and this case does not arise.
Now suppose that
$S=\operatorname {\mathrm {conv}}(R\cup \{v'\})$
. Consider a facet
$G$
that intersects
$F$
at the simplicial
$(d-2)$
-prism
$\operatorname {\mathrm {conv}}\{ w_i, w_i': i=1,\ldots , d-2 \}$
. The facet
$G$
cannot be a pyramid, as
$v$
is not adjacent to
$w_{1}\in G$
and
$\deg _P(v')<2d-2$
. Thus,
$v,v'\in G$
. Furthermore,
$G$
cannot be a simple polytope, since the vertex
$w_{j}$
(with
$j\ne 1,d-1$
) is not simple in
$G$
as it is adjacent to both
$v$
and
$v'$
. From Lemma 2.1, it now follows that
$G$
has
$d+2 (d-2)$
-faces. Since
$w_{d-1}$
is not a simple vertex and since
$f_{k}(P)=\zeta _k(d+s,d)$
for some
$k\in [1, d-2]$
, the computation (3.2) in Subcase 2.1 applies and gives that
$f_{k}(G)=\zeta _k(d+s-2,d-1)$
for some
$k\in [1, d-2]$
. By induction, the facet
$G$
must be one of the nonpyramidal minimizers with
$2d-2$
vertices, namely,
$T\hskip -1.6pt A(d-1)$
or
$W\hskip -1.6pt P$
. Since the
$d-1$
vertices
$w_1', v', w_2, \dots , w_{d-2}$
have degree
$d$
in
$G$
, the facet
$G$
cannot be
$T\hskip -1.6pt A(d-1)$
(Remark 2.6). When
$d=5$
, the degree of
$v$
in
$G$
is 6, so
$G$
cannot be
$W\hskip -1.6pt P$
(Figure 1). Hence, this case does not arise.
It remains to consider the case
$f_0(F_1)=2d-2$
. The proof of Subcase 2.1 gives that
$F_1$
has at least
$d+2$
facets, as it is not a pyramid or a simple polytope. As
$w_1'$
is a nonsimple vertex outside
$F_1$
, the facet
$F_{1}$
is a largest facet with at least
$d+2\; (d-2)$
-faces, and
$f_{k}(P)=\zeta _k(d+s,d)$
for some
$k\in [1, d-2]$
, the computation (3.2) in Subcase 2.1 applies and gives that
$f_{k}(F_{1})=\zeta _k(d+s-2,d-1)$
. In this scenario, the induction hypothesis on
$d-1$
ensures that
$F_1$
is one of the nonpyramidal minimizers with
$2d-2$
vertices, namely,
$T\hskip -1.6pt A(d-1)$
or
$W\hskip -1.6pt P$
. Since
$\deg _{P}(v)=2d-2$
, the degree of
$v$
in
$F_{1}$
is at least
$2d-4$
. Thus, when
$d=5$
, the facet
$F_1$
cannot be
$W\hskip -1.6pt P$
(Figure 1). Consequently,
$F_1$
can be only
$T\hskip -1.6pt A(d-1)$
. By the structure of
$T\hskip -1.6pt A(d-1)$
(Remark 2.6), the degree of
$v$
in
$F_{1}$
is
$2d-4$
, so
$v$
must be adjacent to
$w_{1}$
, and
$v'$
must be simple in
$F_{1}$
. Moreover, without loss of generality, we may assume that
$w_{d-1}$
and
$w_{d-1}'$
are simple in
$F_1$
, and therefore simple in
$P$
. It follows that
$v$
is not adjacent to either
$w_{d-1}$
or
$w_{d-1}'$
.
By the structure of
$T\hskip -1.6pt A(d-1)$
(Remark 2.6), either
$w_i$
or
$w_i'$
is not simple in
$F_{1}$
(for each
$i\ne 1,d-1$
) and therefore not simple in
$P$
, respectively (see Figure 1).
For
$i=2,\ldots ,d-2 $
, consider the other facet
$F_{i}$
in
$P$
containing the
$(d-2)$
-face of
$F$
missing the edge
$[w_{i},w_{i}']$
. None of these facets can be pyramids, as
$v$
cannot be an apex; recall that the vertices
$w_{d-1}$
and
$w_{d-1}'$
are in each such
$F_{i}$
and
$v$
is not adjacent to one of them. None of these facets are simple polytopes, as either
$w_j$
or
$w_j'$
(for
$j\ne i,d-1$
) is nonsimple in
$F_{i}$
. Thus, each
$F_{i}$
has
$d+2$
facets and
$2d-2$
vertices. The same reasoning used with
$F_1$
ensures that the facets
$F_i$
(for
$i=2,\ldots ,d-2$
) are all
$T\hskip -1.6pt A(d-1)$
. Hence, this gives
$d-2$
copies of
$T\hskip -1.6pt A(d-1)$
as facets of
$P$
.
Since
$w_1'$
is adjacent to both
$v'$
and
$v$
, and the vertex
$v'$
is simple in each of the facets
$F_{i}$
, the graph of
$P$
is now clear: the vertex
$v'$
is adjacent to the vertices
$v$
,
$w_1', \dots , w_{d-1}'$
; the vertex
$v$
is adjacent to the vertices
$v'$
,
$w_1',\ldots , w_{d-2}'$
, and
$w_1,\ldots , w_{d-1}$
.
With the graph of
$P$
in place and using Corollary 3.11, we find that the unique facet containing
$v'$
but not
$v$
must be the simplex
$\operatorname {\mathrm {conv}}(R'\cup \{v'\})$
. Since
$w_{d-1}$
is simple in
$P$
, there is a further simplex facet
$\operatorname {\mathrm {conv}}(R\cup \{ v\})$
. Furthermore, the unique facet containing both
$v$
and
$v'$
and intersecting
$F$
at a
$(d-3)$
-face must be the simplex
$\operatorname {\mathrm {conv}}(\{v,v'\}\cup \{w_i': i=1,\dots , d-2\})$
. Hence, this gives three simplex facets of
$P$
.
Since
$v'$
is simple in
$P$
and there are already
$d$
facets containing
$v'$
, the other facet
$F_{d-1}$
in
$P$
containing the
$(d-2)$
-face of
$F$
missing the edge
$[w_{d-1},w_{d-1}']$
, does not contain
$v'$
. Thus,
$F_{d-1}$
must contain
$v$
, implying that
$F_{d-1}$
is an
$M(d-2, 1)$
. We have now produced all the
$d+3$
facets of
$P$
. These facets now give the vertex–facet incidence of the polytope, implying that
$P$
is
$T\hskip -1.6pt A(d)$
.
Remark 3.9(vi) The facet
$F$
has
$d+1$
vertices and is a
$(2,d-3)$
-triplex. Moreover, the vertex
$v$
has degree exactly
$d+1$
. Every vertex outside
$F$
other than
$v$
is simple in the facet of
$P$
containing it but not
$v$
.
As in Case 3 of Theorem 3.6, we denote the
$s-1$
vertices outside
$F$
by
$u_1,\ldots ,u_{s-1}$
where
$u_{1}=v$
. Denote the apices of
$F$
by
$x_1,\ldots ,x_{d-3}$
. For
$i\in [1, d-3]$
, consider the facet
$F_i$
intersecting
$F$
at the
$(d-2)$
-face
$F\setminus \{x_{i}\}$
. It follows that
$F_i$
has exactly
$d+1$
vertices, and so
$F_i$
is a pyramid. No vertex in
$\{u_2,\ldots ,u_{s-1}\}$
can be the apex of
$F_{i}$
, since they need to be simple in the facet containing them but not
$v$
. Thus,
$v$
is the apex of
$F_i$
for each
$i$
. It follows that
$v$
is adjacent to all the vertices of
$F$
, and since the vertices outside a facet form a connected subgraph [Reference Pineda-Villavicencio7, Theorem 4.1.6], the degree of
$v$
in
$P$
would be at least
$d+2$
, contradicting our assumption.
Remark 3.9(vii) The facet
$F$
is a simplex, and so is every facet not containing a vertex of the largest degree. Every vertex outside
$F$
other than
$v$
is simple in every facet of
$P$
containing it but not
$v$
. There is another simplex facet
$F'$
such that
$F\cup F'$
contains
$d+s-1$
vertices.
Suppose that
$s\leqslant d-1$
. By Remark 3.8(i),
$\deg (v)=d+s-1$
, and the same holds for every vertex in
$F \cap F'$
. The vertex figure
$P/v$
of
$v$
is
$M(s, d-s-1)$
. If
$d-s-1\geqslant 1$
,
$P/v$
is a pyramid. Then the polytope is a pyramid: consider the facet containing
$v$
but not containing the vertex in
$P$
corresponding to the apex of
$P/v$
; this facet necessarily contains
$d+s-1$
vertices. The case of
$P$
being a pyramid has already been covered. In case
$d-s-1=0$
,
$P/v$
is a simplicial
$(d-1)$
-prism and
$\# (F\cap F')=2$
. A vertex
$w$
in
$F\cap F'$
has the same degree
$2d-2$
as
$v$
. Denote by
$w'$
a vertex in
$P/v$
corresponding to
$w$
. In
$P/v$
, there is a face that is a simplicial
$(d-2)$
-prism
$R$
and does not contain
$w'$
. In
$P$
, there is a corresponding facet
$J$
that contains
$v$
and
$R$
. The facet
$J$
contains
$v$
but not
$w$
and has
$2d-3$
vertices. The facet
$J$
has more vertices than
$F$
and misses a vertex of largest degree, contrary to our assumption on
$F$
.
Assume that
$s=d$
. By Remark 3.8(ii), we find that
$\deg (v)=2d-2$
and that its vertex figure is a simplicial
$(d-1)$
-prism
$R$
. The prism
$R$
is the convex hull of two
$(d-2)$
-simplices
$\operatorname {\mathrm {conv}}\{w_{1},\ldots ,w_{d-1}\}$
and
$\operatorname {\mathrm {conv}}\{w^{\prime }_{1},\ldots ,w^{\prime }_{d-1}\}$
so that the vertices
$w_{i}$
and
$w_{i}'$
are adjacent. For
$i=1,\dots ,d-1$
, let
$u_{i}$
and
$u^{\prime }_{i}$
represent the vertices in
$F\cup F'$
corresponding to the vertices
$w_{i}, w_{i}'\in P/v$
, respectively. Moreover, the unique vertex
$w\in F\cap F'$
has degree
$2d-2$
and is not adjacent to
$v$
.
For
$i=1,\ldots ,d-1$
, consider the other facet
$J_{i}$
in
$P$
containing
$v$
and arising from the
$(d-2)$
-face of
$R$
missing the edge
$[u_{i},u_{i}']$
. As in Remark 3.8(ii), each facet
$J_{i}$
has
$2d-2$
vertices and contains the vertex
$w$
. If a vertex
$u_{j}$
or
$u_{j}'$
has degree
$2d-3$
in a facet
$J_{i}$
(
$i\ne j$
), then
$J_{i}$
would be missing a vertex of largest degree in
$P$
, contradicting our assumption. Thus, no vertex
$u_{j}$
or
$u_{j}'$
can be an apex of a facet
$J_{i}$
. Each facet
$J_{i}$
is not a pyramid: none of the vertices
$u_{j}$
or
$u_{j}'$
(
$i\ne j$
) can serve as the apex, nor can
$v$
or
$w$
due to their degrees in
$J_{i}$
. Additionally, each facet
$J_{i}$
is not a simple polytope, as both
$v$
and
$w$
have degree
$2d-4$
in
$J_{i}$
. By Lemma 2.1, each facet
$J_{i}$
has at least
$d+2 \;(d-2)$
-faces.
Suppose that, for some
$i\in [1, d-1]$
, the vertex
$u_i$
or
$u_i'$
is not simple in
$P$
. Then,
$J_{i}$
is a facet with
$2d-2$
vertices and at least
$d+2\; (d-2)$
-faces, and since
$f_{k}(P)=\zeta _k(2d,d)$
for some
$k\in [1, d-2]$
, the computation (3.2) in Subcase 2.1 applies and gives that
$f_{k}(J_{i})=\zeta _k(2d-2, d-1)$
. In this scenario, the induction hypothesis on
$d-1$
ensures that
$J_{i}$
is one of the nonpyramidal polytopes in Parts (ii)–(v) of the theorem with
$2(d-1)$
vertices, namely,
$T\hskip -1.6pt A(d-1)$
, or
$W\hskip -1.6pt P$
(Figure 1). In
$T\hskip -1.6pt A(d-1)$
, all the nonsimple vertices are pairwise adjacent, while in
$J_i$
, the vertex
$v$
is not adjacent to
$w$
. If
$J_i$
were
$W\hskip -1.6pt P$
, then
$d=5$
and the degree of
$v$
in
$J_i$
would be
$2d-4=6$
, but no vertex in
$W\hskip -1.6pt P$
has degree six. Hence, this scenario does not arise.
We can now assume that all the vertices
$u_i, u_i'$
are simple in
$P$
. Thus, there are exactly two nonsimple vertices in
$P$
, namely,
$v$
and
$w$
. The graph of
$P$
is determined: there are two disjoint
$(d-2)$
-simplices
$\operatorname {\mathrm {conv}}\{u_{1},\ldots ,u_{d-1}\}$
and
$\operatorname {\mathrm {conv}}\{u^{\prime }_{1},\ldots ,u^{\prime }_{d-1}\}$
whose vertices are all adjacent to both
$v$
and
$w$
. However, this is not the graph of a
$d$
-polytope with
$d\geqslant 5$
, as the removal of
$v$
and
$w$
would disconnect the graph, contradicting the vertex
$d$
-connectivity of the graph by Balinski’s theorem [Reference Balinski1].
Open access
