matthias beck

Fall 2015

Course objectives. A central theme of combinatorics is given by counting functions that are polynomials, and these counting functions will form the point of departure in this course. For example, in an attempt to prove the Four-Color Conjecture (now a theorem), George Birkhoff famously introduced a function c_G(k) that counts all proper k-colorings of a graph G, i.e., assignments of k colors to the nodes of G such that any two adjacent nodes get different colors. It turns out that c_G(k) is a polynomial in k (the chromatic polynomial of G) which captures much more data than the number of possible colorings. For example, Richard Stanley proved that there are |c_G(-1)| ways to orient G in such a way that there is no coherently oriented cycle.

The three major themes in this course, paralleling its name, are generating functions (enumeration), polyhedra (geometry), and partially ordered sets (combinatorics). We will develop each theme from scratch (though on a graduate level, we only require the background from a typical undergraduate course in linear algebra) and illustrate that the most powerful theory--and practical applications--come from combining all three themes. For example, we will establish geometric reasons why c_G(k) is a polynomial and why |c_G(-1)| counts the acyclic orientations of G.

Prerequisites. Undergraduate Linear Algebra and familiarity with basic combinatorial objects.

Text book: M. Beck and R. Sanyal, Combinatorial Reciprocity Theorems, American Mathematical Society (to appear).
Useful references include:

• M. Beck and S. Robins, Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra, Springer 2007 & 2015
• J. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, Springer 2010.
• R. Stanley, Enumerative Combinatorics I, Cambridge 2012.
• G. Ziegler, Lectures on Polytopes, Springer 1995.

Syllabus: I plan to cover most of Chapters 2-6 in the text book, that is:

• Partially ordered sets: incidence algebra, Mobius inversion, zeta polynomials, and order polynomials
• Polyhedral geometry: polytopes and cones, Euler characteristic, face lattices, hyperplane arrangements
• Rational generating functions: partition analysis, quasipolynomials, Stanley reciprocity for rational cones
• Subdivisions: triangulations, half-open decompositions, Ehrhart polynomials
• Order cones: order polynomials revisited, order polytopes, permutation statistics, P-partitions

Grading system: I will assign weekly homework problems, due on Thursdays before class (90% of the final grade). In addition, every student will give one lecture on the material we will cover (10% of the final grade; here is a list of possible topics).

I want to ensure that each of you accomplishes the goals of this course as comfortably and successfully as possible. At any time you feel overwhelmed or lost, please come and talk with me.

Fine print.
SFSU academic calender
BS rule
Academic integrity and plagiarism
Tutoring
CR/NCR grading
Incomplete grades
Late and retroactive withdrawals
Students with disabilities
Religious holidays

This syllabus is subject to change. All assignments, as well as other announcements on tests, policies, etc., are given in class. If you miss a class, it is your responsibility to find out what's going on. I will try to keep this course web page as updated as possible, however, the most recent information will always be given in class. Always ask lots of questions in class; my courses are interactive. You are always encouraged to see me in my office.