# Number of facets of a polyhedron when a vertex is removed

My question, informally: I have a bounded polyhedron in R^n with k facets, and I want to remove a vertex of this problem. How many facets does the remaining polyhedron have at most?

More formally: Let P be a polyhedron in R^n. Then P = conv (vert P), where "vert P" gives the vertices of P and "conv" gives the convex hull of a set of points. I'm wondering whether there is an upper bound on the number of facets of conv (vert P \ { v }), where v is a vertex of P.

A simple upper bound is the following one: Using the Upper Bound Theorem, we can determine the maximum number of vertices for any polyhedron with k facets. Let this number be V. Then we can use the Upper Bound Theorem again to determine the maximum number of facets for any polyhedron with V - 1 vertices. This bound, however, seems very conservative.

Does anybody have an idea about a tighter bound? Any help would be much appreciated!

Thanks to everybody for the examples of "bad cases" where the removal of a vertex introduces many new facets. They confirm my suspicion that the number of facets can indeed grow significantly. I was wondering whether one can derive a non-trivial upper bound on the number of facets thereby introduced?

• It is very easy to imagine a situation where removal of a vertex results in a significantly more complicated polytope. By the way, I would not call this "chopping off a vertex". That term I would reserve to adding additional inequality that would remove a little piece of the polytope next to a vertex (and give one more face). – Lev Borisov Feb 5 '16 at 19:21
• Take a cone over a complicated polytope in $\mathbb R^{n-1}$, i.e. a convex hull of some points of the form $(w_i,0)$ and $({\bf 0},1)$. Then wiggle the points $(w_i,0)$ to $(w_i,\epsilon_i)$. When you remove the vertex $({\bf 0},1)$, the new number of facets is equal to the number of simplices in a regular triangulation of $conv(\{w_i\})$. I think that this could be significantly larger than the number of facets of $conv(\{w_i\})$. – Lev Borisov Feb 5 '16 at 19:31
• I suggest rephrasing "chopped off," which suggests truncation, to "removal," which is what is intended. – Joseph O'Rourke Feb 6 '16 at 2:29

Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull. Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$. That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$. It is easy to check that the following system completely describes $P(G)$. $$0 \le z_v \le 1, \text{ for all v \in V(G)} \\ 0 \le y_{vw} \leq z_v, \text{ for all vw \in E(G)}.$$ Thus, $P(G)$ has $O(V(G)+E(G))$ facets.

Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs. Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. $$y(F) \leq z(V(G))-1, \text{ for all spanning forests F of G}.$$

Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.

• Thank you for the example! Do you have any idea on how one could derive a non-trivial upper bound on the number of facets introduced by removing a vertex? – Vera Deschamps Feb 7 '16 at 10:50

When removing vertex $v$ by slicing by an $n-1$ dimensional plane $S$ in such a way that no other vertex is sliced off, every facet that includes $v$ transforms to a facet with an additional boundary component, but that is still just one facet. And the intersection of the plane $S$ with the original polyhedron is the boundary of one additional facet, lying in $S$. Therefore, the upper bound is $k+1$ facets.

This upper bound is always saturated unless $S$ slices through some vertiex or vertices other than $v$. For example, in a cube, if you slice off a little triangle near to one corner you are left with $6+1=7$ facets, one of which is a triangle, three pentagons, and three squares. But if the slice passes through the three vertices connected by an edge to that corner, the facets go down to $4$, three triangles and a quadrilateral.

However, in the last paragraph of the problem it becomes clear that this is not what the OP means, because he speaks of a polyhedron with $V-1$ vertices, and teh polyhedra formed by plane slicing have, in may cases, more than $V$ vertices. (For example, the cube with a corner nipped has ten vertices.)

If you are restricted to lopping of a vertex such that no new vertices are created, then the most remaining facets are achieved when the slicing loses every facet attached to $v$ and gains the single new facet. Now in $n$ dimensions each vertex intersects with at least $n$ facets. So the upper bound, achieved when slicing off a vertex that is in with just $n$ facets in such a way that the slicer goes through edges only at other vertices, is $k-n+1$.

Obviously, for a generic polyhedron, it may or may not be possible to slice off a specific vertex without creating new vertices, so this upper bound is not always achievable.

• The OP assigns a rather nonstandard meaning to "chopping off a vertex". – Lev Borisov Feb 5 '16 at 21:36
• Thanks for the response, and apologies for not being clear in my original question! – Vera Deschamps Feb 7 '16 at 10:51