How many vertices of a polytope can be chopped off to produce a k-vertex facet?

Question

Let P be a simple n-facet d-polytope with facet F, and let F have k vertices. Let H be a halfspace and Q be a simple (n-1)-facet polytope such that H ∩ Q = P.

In terms of k, what is an upper bound on the number of vertices of Q contained in (ℝ^d \ H)? Informally: what is the largest number of vertices of Q that can be chopped off to produce a k-vertex facet F?

I've derived an algorithm to compute this value exactly in terms of the f-vector of F, but I'd like to determine a tight upper bound when the f-vector is unavailable.

Some observations: The removed set of vertices cannot contain a facet of Q, thus there would seem to be an upper limit on its size. k ≥ d, naturally, since cutting off a single vertex produces d vertices.

If this question is particularly difficult or contains any open problems of which I'm not aware, I'd be interested in knowing that, too!

Answer 1

I doubt this is anywhere close to tight, but here's a proof that it's bounded. The new facet has k vertices, so by the upper bound theorem it has $O(k^{\lfloor (d-1)/2\rfloor})$ ridges. Every facet of the polytope you cut off is either $F$ itself or a facet through one of these ridges, so there are $O(k^{\lfloor (d-1)/2\rfloor})$ facets of the cut-off polytope. Applying the upper bound theorem again, it has $O((k^{\lfloor (d-1)/2\rfloor})^{\lfloor d/2\rfloor})$ vertices.

This works without the assumption of simplicity. Using the fact that all your polytopes are simple you get at most k ridges directly, and $O(k^{\lfloor d/2\rfloor})$ vertices, I think.

Answer 2

In three dimensions look at the prism whose ends are two regular polygons with $k$ sides. Look at the plane close to one end parallel to the plane containing one regular polygon that cuts of the regular polygon. Then that would satisfy all the conditions of the problem except one it cuts off one face. The plane can be rotated through a line close to one vertex so that it cuts off all vertices except that vertex. Then it will cut off $k-1$ points and leave all the original faces intact. It will have $k+1$ vertices So in three dimensions at least $k-1$ vertices can be cut off by a facet with $k+1$ vertices without losing any of the original faces. I think this technique can be used in higher dimensions.

If $v$ vertices are cut off by a plane which intersects a polyhedron in a polygon with $k$ sides with no faces cut off then the cut off polyhedron will have $k+1$ faces. As David Eppstein has observed in his answer to this question every facet of the polytope you cut off is either $F$ the face formed by the cutting hyperplane here a plane which cuts the polyhedron in a polygon with $k$ edges itself or a facet through one of these ridges,so in the two dimensional case this gives $k+1$ faces.

The edges connecting the vertices cut off must form a tree. They contain no cycle or else a face would be cut off. They are connected since removing the edges of a face of polyhedron leaves the graph of the remaining edges connected. So these edges form a tree.

We have edges of the graph of a polyhedron equal the sum of the faces and the vertices-2. We know the number of vertices and faces in the polyhedron cut of by the plane. The vertices are $v + k$, and there are $k+1$ faces. So we must have $v + 2k-1$ edges we have $k$ edges formed by the vertices of the polygon F and $v-1$ from the tree formed by the vertices cut off. The only possiblity left is vertices between the cut of vertices and the vertices of $F$. Since each point must be adjacent to three edges each point of the polygon must have one edge which touches the cut of vertices. There must be $v+2$ edges in addtion to the edges of the tree to make every cut off vertex adjacent to exactly three edges. thus $k$ edges must equal $v+2$ edges and $k=v+2$.

So in three dimensions every cut that doesn't remove a face and intersects a polyhedron in $k$ vertices cuts of $k-2$ vertices. In higher dimensions I am not sure what happens. I know that there examples when $k$ vertices cut off $k-d$ vertices but beyond that I am not sure.