DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

Candidate: N.PRABHU

Advisor: RICHARD POLLACK

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]

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*R*^{d}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.