Math 581GA-582GA-583GA
Foundations of Combinatorics

581GA and 582GA (Sarah Billey), 583GA (Isabella Novik)

Autumn 2003, Winter 2004 and Spring 2004, Monday-Wednesday-Friday 12:30-1:20
This three-quarter topics course on combinatorics includes Enumeration, Graph Theory, and Polytopes. Combinatorics has connections to all areas of mathematics and many other sciences, including biology, physics, computer science, and chemistry. We have chosen core areas of study that should be relevant to a wide audience. The main distinction between this course and its undergraduate counterpart will be the pace and depth of coverage. Unsolved problems and directions for future research will be included.

Prerequisites: Students should have a basic knowledge of linear and abstract algebra.

Note: Although, we advise students to take all three quarters, a sophisticated student could certainly take any one of the three quarters alone.

581GA: Enumeration.

Every discrete process leads to questions of existence, enumeration and optimization. This is the foundation of combinatorics. In this quarter, we will present the basic combinatorial objects and methods for counting various arrangements of these objects.
Topics.
(a) basic counting methods, (b) sets, multisets, permutations, and graphs, (c) inclusion-exclusion, (d) recurrence relations and integer sequences, (e) generating functions, (f) partially ordered sets, (g) complexity theory.
Tentative Text:
Enumerative Combinatorics; Volume 1 by Richard Stanley, Cambridge Studies in Advanced Mathematics, 49, 1997.

582GA: Graph Theory.

Graphs are among the most important structures in combinatorics. They are universally applicable for modeling discrete processes. We will introduce the fundamental concepts and some of the major theorems. The existence questions of combinatorics are prevalent in graph theory.

Topics:
(a) basic graph structures, (b) matchings, (c) planar graphs, (d) colorings, (e) Ramsey theory, (f) random graphs and probabilistic methods, (g) graph minor theorem.

Tentative Text:
Graph Theory by Reinhard Diestel, Spring-Verlag, GTM 173, 2nd Ed., 2000. Electronic version: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory.

583GA: Combinatorics of Polytopes.

Polytopes are simple objects (defined as the convex hull of a finite set of points in Rn), yet they have a rich and continuously developing theory. While 3-dimensional polytopes are well understood, many obvious results in dimension 3 are either false or unknown in higher dimensions. This course addresses certain combinatorial properties of polytopes.
Topics:
I. Graphs of polytopes: (a) Steinitz' theorem for 3-polytopes, (b) Balinski's theorem, (c) reconstructing simple polytopes from their graphs, (d) the Hirsh conjecture.

II. Face numbers of simplicial polytopes: (a) Dehn-Sommerville equations, (b) the Upper Bound Theorem, (c) the Lower Bound Theorem, (d) the g-theorem and its consequences, (e) face numbers of centrally symmetric polytopes, (f) extensions to more general classes of simplicial complexes.

III. Gale diagrams and various counterexamples.