# Vertices of a Polytope

Given two convex polytopes $P,Q$ such that $P\subset Q$. We are given that all the vertices of $P$ are also vertices of $Q$ and all the facets defining planes of $Q$ are also facets defining planes of $P$. If $V_P$ is the set of vertices of $P$ and $V_Q$ is the set of vertices of $Q$, we want to estimate $\lvert V_Q\setminus V_P\rvert$ possibly in terms of the dimension of $P$ (or $Q$, since both have the same dimension).

An example when $P\neq Q$:

$P=conv([0,0,1],[0,1,0],[1,0,0],[1,1,0],[1,0,1],[0,1,1])$ $Q=conv([0,0,0],[0,0,1],[0,1,0],[1,0,0],[1,1,0],[1,0,1],[0,1,1])$

(Credit to Prof. Shashank K Mehta for constructing the above example)

See the figures below:  • I think $V_P \subset V_Q$ by assumption, which is correct. However, the condition on the facets will imply $V_Q \subset V_P$, in'nit? ... – SashaKolpakov Oct 1 '13 at 17:38
• "By facets I meant the facet defining planes": This nonstandard use of the term facet is why your question has been misinterpreted. – Joseph O'Rourke Oct 2 '13 at 11:32
• @ARi I have added an example – Pawan Aurora Oct 7 '13 at 15:27

$Q$ can have arbitrarily many more vertices than $P$, even in 3 dimensions.

1. Suppose $v$ is a vertex of degree 3 in $Q$ (degree $d$, in $d$ dimensions), and the three incident faces are not triangles (simplices, in general dimensions). Then one can cut off $v$ by a triangle through the three neighbors $a$, $b$, $c$ of $v$. The resulting polytope $P$ has one vertex less ($v$) and an additional face $abc$, and all original facial planes of $Q$ remain. (Faces might become smaller.) The given example is constructed in this way: $v$ is the origin. One could also take the cube as the starting polytope $Q$.

2. If there are many such vertices $v$ "sufficiently far apart" (maybe distance 5 or 6 suffices), they can all be cut off simultaneously without losing a face completely.

3. To get such a polytope where many vertices can be cut off, take the given example polytope and squish it in the direction $(1,1,1)$ by a linear transformation with the matrix $\frac13\cdot\begin{pmatrix}2+\alpha&-1+\alpha&-1+\alpha\\ -1+\alpha&2+\alpha&-1+\alpha\\ -1+\alpha&-1+\alpha&2+\alpha \end{pmatrix}$ for very small $\alpha$. It will be almost flat, lying close to the plane $x+y+z=0$. Now take a polytope with many faces add a small copy of this flat gadget on top of each face.

• @GuenterRote: in dimension three you may wish to consider fullerenes (liga.ens.fr/~deza/Sem-FullCCirmVirusSpFull/FFullereneConf.pdf) as an example of polytopes with many vertices of degree 3 sufficiently far from each other. I think it works, when you cut a number of vertices of a fullerene by triangles, since fullerenes have 5- and 6-gonal faces only. The number of vertices of a fullerene is generally unbounded. – SashaKolpakov Oct 8 '13 at 3:13
• Indeed, fullerenes are a good example. Almost all of the surface is a hexagonal lattice, and there you can simultaneously cut away vertices as long as their minimum distance is 2. Thus, you can cut away half of the vertices (almost; staying away from the pentagons). – Günter Rote Oct 8 '13 at 6:46

Every convex polytope is a convex hull of its vertices. Thus, if the vertices of $P$ are a subset of the vertices of $Q$, we immediately have that $P \subset Q$. Since all the facets of $Q$ are a subset of the facets of $P$, then the vertices of $Q$ are a subset of the vertices of $P$ (just take all the facets of $Q$ and you will collect all its vertices, as well). Thus, looking at the respective convex hulls, we get $Q \subset P$. Please correct me if I'm in error or misunderstood something in your question.

A little addition: I wrongly supposed before that $P=Q$, even if we consider facet defining hyperplanes instead of facets . Indeed each defining hyperplane $H_F$ (for a facet $F$) defines a half-space $H^{+}_F$, and $P = \cap_{F \in F_P} H^{+}_F$, for the half-spaces corresponding to the facets $F_P$ of $P$. Same $Q = \cap_{F\in F_Q} H^{+}_F$. Since $F_Q \subset F_P$, we have $P \subset Q$ but not necessarily $P = Q$. Once $F_P$ contains an additional hyperplane $H$, compared to $F_Q$, then it necessarily generates additional intersections with other hyperplanes defining the facets of $P$ (compare the representations of $P$ and $Q$ as intersections of half-spaces) and, thus, additional vertices of $P$, compared to $Q$, may appear. However, the new hyperplane may go through some old vertices of $Q$, cutting of a part of it (with some other vertices), as in the example. This is a method of obtaining polytopes with the desired property: take $P$, find a hyperplane going through some of its vertices and intersecting it only at these vertices, then cut $P$ into pieces along that hyperplane. Then we obtain $Q$, having lesser vertices and more facet defining planes. I'm not quite sure, if this is the only way of getting such pairs $P$ and $Q$, or not.

A little addition 2: As Guenter Rote already said, there could be unbounded difference in the number of vertices, if you cut out an "old" vertex of $P$ by a plane going through exactly three other "old" vertices, and thus obtain $Q$ with one lesser vertex, and one more triangular plane. As an example of a family of polytopes $P_n$ (dimension three) with many vertices of valence three, which you can cut out by triangles, and where many vertices are at sufficient distance from each other, you may wish to consider fullerenes (http://www.liga.ens.fr/~deza/Sem-FullCCirmVirusSpFull/FFullereneConf.pdf). Then the number of possible cut-off vertices is unbounded as $n$ grows.

• By facets I meant the facet defining planes. So consider a pentagon and a triangle inside it formed by three of its vertices. Both have the same facet defining plane but not the same set of vertices. – Pawan Aurora Oct 2 '13 at 2:27
• Please see the example I have added to the question – Pawan Aurora Oct 7 '13 at 15:29
• Thank you! Now I see where I was wrong about the case when you consider facet defining hyperplanes instead of faces: F_P definitely has a new hyperplane, but when it intersects those already in F_Q, it may happen that no new vertices appear (thus, the new hyperplane has to go through some "old" vertices and may chop off some other "old" vertices. – SashaKolpakov Oct 7 '13 at 17:00
• @PawanAurora: I edited my (partially wrong) answer. I will see if I can say anything more now, when you clarified the situation with that nice example. – SashaKolpakov Oct 7 '13 at 17:13