matthias beck

some of matt's pictures
MATH 890

Polytopes and Varieties:

Enumerative Geometric Combinatorics

Fall 2015

Lecture Tue/Thu 9:35-10:50 Hensill 667
Instructor Dr. Matthias Beck
Office Thornton Hall 933
Office hours Tue 11-12 & 5-6, Thu 2-3, 6-7 & by appointment

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 cG(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 cG(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 |cG(-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 cG(k) is a polynomial and why |cG(-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:

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
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.

SF State Home