Math 581B/582B/583C
Foundations of Combinatorics

Sara Billey

Autumn 2005/Winter 2006/Spring 2006, Monday/Wednesday/Friday, 10:30
This three-quarter topics course on combinatorics includes Enumeration, Graph Theory, and Symmetric Functions. This three quarter topics course on combinatorics includes Enumeration, Graph Theory, and Symmetric Functions. 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. We will include unsolved problems and directions for future research will be included.

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

581B: 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.

582B: 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.

583C: Symmetric Functions.

The symmetric group Sn acts on polynomials in n variables simply by permuting the variable. Polynomials which are fixed under this action are called symmetric polynomials. If we consider the limit as n approaches infinity we get symmetric functions. The symmetric functions appear in many areas of mathematics including algebra, topology, combinatorics, and geometry. The Schur functions are an important basis for symmetric functions. Once key application of symmetric function theory using Schur functions is the representation theory of Sn. Another key application of symmetric function theory is to the study of the cohomology ring of the Grassmannian manifold. Recently, a generalization of Schur functions known as Macdonald polynomials has become a very hot topic in research; we will briefly cover their relationship with the n!-Theorem and Hilbert schemes.
Topics:
(a) Partitions and tableaux,
(b) Elementary and homogeneous symmetric functions,
(c) Schur functions and the Littlewood-Richardson rule,
(d) Character theory of Sn,
(e) Representation theory GLn.
(f) Grassmannian manifold,
(g) Macdonald symmetric functions.

Tentative Textbook Selection:

  1. Enumerative Combinatorics; Volume 1 by Richard Stanley, Cambridge Studies in Advanced Mathematics, 49, 1997.
  2. Enumerative Combinatorics; Volume 2 by Richard Stanley, Cambridge Studies in Advanced Mathematics, 62, 1999.
  3. 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.
  4. Young Tableaux by William Fulton, Cambridge University Press, 1997.