Wednesday 17 October 2007

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

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!

No comments:

Post a Comment