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!

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?

My question, informally: I have a bounded polyhedron in R^n with k facets, and I want to chop off 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!

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!