DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE


Candidate: N.PRABHU
Advisor: RICHARD POLLACK

PROPERTIES OF CONVEX POLYTOPES
10:00 a.m., Wednesday, July 10, 1991
rm. 1302, Warren Weaver Hall
[.25in] Abstract

The thesis presents some results about the boundary complexes of convex polytopes.

1.
The intersection of affine subspaces with the boundary complexes of convex polytopes: We show that the lower bound on the dimension of a subspace that intersects the relative interiors of all j-faces of a d-polytope is 2(d-j). We also show that every d-simplex attains the above lower bound; hence the bound is tight. Further, using neighborly polytopes, we construct polytopes with arbitrarily large number of vertices which attain the above lower bound.
2.
Hamiltonian simple polytopes: Given integers n and d, n>d,does there exist a simple d-polytope with n vertices? We show that for all $n > c d\sqrt{d}$ (c a constant) one can construct a simple d-polytope with n vertices. In fact for all $n>c d \sqrt{d},$ we construct a Hamiltonian simple d-polytope with n vertices. The Hamiltonicity of the constructed polytopes improves a result of Victor Klee.
3.
Construction of a 4-dimensional polytope to show that in general one cannot find a hyperplane in Rd that contains a given pair of vertices of a d-polytope and has two or more facets of the polytope in one of the closed halfspaces.
4.
A generalization of Balinski's Theorem: Balinski showed that the graph of every d-polytope is d-connected, i.e., removing any d-1 vertices does not disconnect the remaining subgraph. However, removing all the vertices of a j-face (j<d) leaves the remaining subgraph (d-j-1)-connected and this bound is tight for j<d-1.
5.
A conjecture of Micha Perles: Perles conjectured that every induced, connected, (d-1)-regular subgraph of the graph of a simple d-polytope determines a facet of the polytope. Generalizing Perles' conjecture to triangulated spheres, leads to a question about the existence of a certain triangulation of the 3-ball and the solid torus. We show that neither the 3-ball nor the solid torus admits the required triangulation. Further we prove Perles' conjecture for some subclasses of simple polytopes and prove a few reduction theorems.