18.997: Polytopes

Instructor: Michel Goemans.

Mondays and Wednesdays (not Tuesdays and Thursdays as appeared earlier) 9:30-11 in 2-132.
First meeting Feb 5th!

 The schedule can be found here. 

 For those scribing, here is a basic preamble.tex file
with environment definitions for theorems, proofs, etc. and a short template file
for your scribe notes.

 Here is a list of exercises. And a few references.

 In this course we will study polytopes, mostly from a combinatorial
point-of-view but also at times from an algorithmic
perspective. Polytopes are geometric objects which are simple to
define (bounded intersection of finitely many halfspaces), yet there
are lots of basic questions which are still unanswered (Hirsch
conjecture on the diameter, Mihail and Vazirani's conjecture on the
edge expansion of 0-1 polytopes, ...) or for which known proofs are
rather involved (e.g. Rivin's result on the inscribability of
3-polytopes). Intuition from 3-polytopes usually does not carry
through to higher dimensions.

 Our main reference will be Günter Ziegler's "Lectures on
Polytopes", Springer-Verlag, 1995. We will also discuss topics which
are not much covered in this reference (such as volume of polytopes,
polyhedral combinatorics,...) and hopefully recent results (such as
Barany and Por's bound on the number of facets of 0-1 polytopes). We
will start from the basics and no specific prerequisites will be
assumed. The syllabus will partly depend on students' interests but
here is a partial list of the topics we will be discussing.

 
 Representation theorem, Fourier-Motzkin, Caratheodory's theorem. 
 Faces, face lattice, polarity. 
 Hirsch conjecture (special cases, counterexamples, 
subexponential bounds, ...)
 Representation of 3-d polytopes (Steinitz, rubber band
representation, Koebe-Andreev-Thurston circle packing representation)
 Polyhedral combinatorics (i.e. polyhedra and optimization):
illustrative examples (e.g. non-bipartite matchings), techniques,
adjacency, ...
 Shellability. Euler-Poicare formula. Upper bound Theorem. 
 Number of facets for 0-1 polytopes, also for "round" polytopes (+
Fritz John's ellipsoid approximation) and centrally symmetric polytopes
 Volumes of polytopes (formulas, hardness (Barany-Furedi), algorithms, ...)