Number of facets of a polyhedron when a vertex is removed

Question

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?

Answer 1

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)$.

Answer 2

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.