Math 189 -- Special Topics Course, Spring 2004
Geometric Combinatorics and Polytopes

Professor Francis Su
x73616, su @
Office Hours: MON 3:30-5 pm.

Course Content: Geometric combinatorics refers to a growing body of mathematics concerned with understanding the combinatorics associated with discrete geometric objects desribed by a finite set of building blocks. One primary example we will study in this course are polytopes, which are bounded polyhedra and the convex hull of a finite sets of points. We will also study objects built up from polytopes, such as triangulations and cell complexes, and other objects from the land of discrete geometry, such as the arrangements of points, lines, and hyperplanes. There are many connections to linear algebra, discrete mathematics, geometry, and topology--- and there are many exciting applications to other fields such as economics, robotics, and biology. A tentative sample of topics include:

  1. Combinatorial convexity: affine geometry and Radon's theorem
  2. Set intersections: the Helly and KKM theorems and others
  3. Many ways to cut a diamond: polyhedra and polytopes
  4. Thinking in high dimensions: Schlegel diagrams and other devices
  5. The many faces of a polytope: Euler's theorem, upper bound theorem
  6. Our LEGO's: triangulations and simplicial complexes
  7. Counting points to compute volumes: Pick's theorem and Ehrhart polynomials.
  8. Hyperplane arrangements, zonotopes
  9. Combinatorial fixed point theorems and applications to fair division
  10. Ham Sandwich type theorems, Kneser colorings of graphs
  11. Tropical geometry and the space of phylogenetic trees

Course materials: Taking notes in class will be essential, but I will also provide and outline of the main theorems on downloadable notes on the course webpage. Also, for some inexpensive model-building material later on, please buy some gumdrops (I recommend DOTS) and a box of toothpicks (available at, e.g., Target).

Prerequisites: Linear Algebra (Math 12 and Math 63-[corequisite OK]), Discrete Mathematics (Math 55), and an interest in geometry and combinatorics.

Coursework: Homeworks, assigned weekly and due Tuesdays in class, will be announced on the course webpage: These will be worth 30 percent of the course grade.
There will be a midterm, tentatively handed out on March 9, worth 30 percent.
There will be a final project and presentation, worth 40 percent.

Honor Code: All are expected to abide by the HMC honor code. Cooperation is ENCOURAGED in this class, but write up all solutions individually and be sure to credit any collaborators.

HW Assignments
HW #1 (due 1/27) See Exercises at end of Chapter 1.

Available only within Claremont.

HW #2 (due 2/3) See Exercises at end of Chapter 2.

Available only within Claremont.