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