McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Wednesday, December 8th, 1999
TIME: 4:30pm-5:30pm
PLACE: McConnell 320
TITLE: Inner Diagonals of Convex Polytopes
SPEAKER: David Bremner, University of Washington 

An inner diagonal of a polytope P is a segment that joins two vertices of P and that lies, except for its ends, in P's relative interior. A tantalizing conjecture due to von Stengel claims that among simple d-polytopes with 2d facets, the maximum number of inner diagonals is achieved by a d-cube.

In this talk I will present a characterization of the maximum and minimum number of inner diagonals achievable in 3 dimensions for fixed numbers of vertices or facets. I will also present partial results in higher dimensions, including an interesting relationship to Kalai's new proof (based on rigidity of graphs) of the Lower Bound Theorem.

The paper appeared in the July 1999 issue of Journal of Combinatorial Theory, Series A. There is an electronic reprint at:

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at