3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Lev Borisov Feb 5 '16 at 19:21
  • $\begingroup$ 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\})$. $\endgroup$ – Lev Borisov Feb 5 '16 at 19:31
  • 1
    $\begingroup$ I suggest rephrasing "chopped off," which suggests truncation, to "removal," which is what is intended. $\endgroup$ – Joseph O'Rourke Feb 6 '16 at 2:29
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Vera Deschamps Feb 7 '16 at 10:50
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.