| Lecture: | Tuesday 9:00-10:30 | Seminarraum 2 (Geometrie) (NT04064) - Webex Video Conference |
| Exercises: | Tuesday 10:45-11:30 | Seminarraum 2 (Geometrie) (NT04064) - Webex Video Conference |
The content of this course lies at the interplay between enumerative and geometric combinatorics. The main theme will be the study of a fascinating phenomenon known as combinatorial reciprocity, which relates the enumeration of two families of combinatorial objects through the evaluation of a polynomial at positive and negative integers. The main objective is to develop combinatorial and geometric tools to explain combinatorial reciprocities. In the process, we will learn about partially ordered sets and order polynomials; colorings of graphs, acyclic orientations and flows; and counting regions of hyperplane arrangements among others. We will also see how the geometry of convex polytopes and polyhedra can beautifully explain many of the combinatorial results presented in this course.
The course is offered to master and PhD students as part of the module ''Grundthemen Diskrete Mathematik''.
| [1] | Matthias Beck and Raman Sanyal, Combinatorial Reciprocity Theorems: An Invitation to Enumerative Geometric Combinatorics, Graduate Studies in Mathematics, 195. American Mathematical Society, Providence, RI, 2018. |
| [2] | Richard Stanley, Combinatorial reciprocity theorems, Advances in Mathematics 14 (1974), 194-253. |
| [3] | Günter Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995. |
(this is not final, it will be updated weekly)
| Date | Lecture notes | Exercises | Contents |
| Oct. 6 | Lecture 0 | Vorbeschprechung | |
| Oct. 13 | Lecture 1 | Exercise Sheet 1 | What is combinatorial reciprocity? Example 1: graph colorings and acyclic orientations. Proof of combinatorial reciprocity using deletion-contraction arguments. |
| Oct. 20 | Lecture 2 | Exercise Sheet 2 | Example 2: Flows on graphs. |
| Oct. 27 | Lecture 3 | Exercise Sheet 3 | Example 3: Order polynomials. Chromatic polynomial of a graph as a sum of order polynomials. |
| Nov. 3 | Lecture cancelled. | ||
| Nov. 10 | Lecture 4 | Exercise Sheet 4 | Example 4: Ehrhart polynomials in the plane. Proof of combinatorial reciprocity using triangulations of polygons. |
| Nov. 17 | Lecture 5 | Exercise Sheet 5 | Combinatorial proof of order polynomial reciprocity. Part 1: order polynomials as powers of zeta functions. |
| Nov. 24 | Lecture 6 | Exercise Sheet 6 | Combinatorial proof of order polynomial reciprocity. Part 2: order polynomials evaluated at -n as powers of Möbius functions. |
| Dec. 1 | Lecture 7 | Exercise Sheet 7 | Towards Ehrhart polynomials in higher dimensions. Preliminaries 1: Introduction to polyhedral geometry. |
| Dec. 15 | Lecture 8 | Exercise Sheet 8 | Polyhedral geometry: polyhedra, polytopes, faces, Euler characteristic, and Möbius function. |
| Jan. 12 | Lecture 9 | Exercise Sheet 9 | Preliminaries 2: Generating functions |
| Jan. 19 | Lecture 10 | Exercise Sheet 10 | Generating functions reciprocity. Stanley's reciprocity for simplicial cones. |
| Jan. 26 | Lecture 11 | Exercise Sheet 11 | Ehrhart-Macdonald reciprocity. Applications: reciprocity for order polynomials and chromatic polynomials geometrically. |
Holidays and University Closings: Dec. 8 (Maria Empfängnis), Dec. 21-Jan. 6 (Weihnachtsferien).