Combinatorial Reciprocity Theorems

Summer Semester 2014

Prof. Raman Sanyal, Arnimallee 2, room 105

Katharina Jochemko , Arnimallee 2, room 105



lecture monday 10-12 Arnimallee 6 SR 025/026
recitation tuesday 14-16 Arnimallee 6 SR 025/026


Colorings of a graph, order preserving maps into a chain, and points outside a hyperplane arrangement over a finite field are just some examples of combinatorial structures whose counting functions are polynomials. A combinatorial reciprocity theorem is a form of duality that relates combinatorial structures via their counting functions. Informally: The counting function of the one is the counting function of the other at negative integers. In this course we will view such reciprocities from the perspective of geometric combinatorics. To that end we will develop the necessary theory of partially ordered sets and Moebius functions, polytopes, hyperplane arrangements, triangulations, and Ehrhart theory.

This course is aimed at beginning graduate/master students with an interest in combinatorics and discrete geometry. The course is part of the module "Diskrete Geometrie".


Together with Matthias Beck I am writing a book on combinatorial reciprocity theorems. The lastest version of our book draft will be incrementally posted here (after each lecture). A much older version of our book can be found here but I do not recommend that you print it.
[BS] Felix Breuer, Raman Sanyal, Ehrhart theory, Modular flow reciprocity, and the Tutte polynomial, Math. Zeitschrift, 2010, in print
[Gr] Branko Grünbaum Convex Polytopes, Springer GTM 221
[R] Gian-Carlo Rota On the foundations of combinatorial theory I. Theory of Möbius Functions, Probab. Theory Related Fields 2 (1964), 340-368
[St1] Richard Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194-253.
[St2] Richard Stanley, Enumerative Combinatorics, volume 1, second edition
[W] Herbert Wilf, generatingfunctionology, second edition
[Z] Günter Ziegler, Lectures on Polytopes, Springer GTM 152


You have to hand in the homeworks on Monday before the lecture.
Homework #10 due July 14
Homework #9 due July 7
Homework #8 due June 30
Homework #7 due June 17
Homework #6 due June 2
Homework #5 due May 26
Homework #4 due May 19
Homework #3 due May 12
Homework #2 due May 5
Homework #1 due April 28

what happend so far (up-to-date book draft is here)

June 10 Euler-Poincare formula; Euler characteristic for polytopes via homogenizations; Möbius function of face lattices
May 26 wrap-up order polynomials: Birkhoff's theorem on distributive lattices, Zeta polynomials, and Eulerian posets; polyconvex sets and Euler characteristic (statement); hyperplane arrangements and H-polyconvex sets
May 19 Introduction to polyhedral geometry: Convex polyhedra and polytopes; dimension, relative interior and lineality space; cones and homogenization; Minkowski-Weyl theorem; Faces and face lattice
May 12 zeta function of a poset; powers and counting chains; order polynomial as powers of zeta; invertible elements and Möbius functions; the Möbius function of the Birkhoff lattice; proof of combinatorial reciprocity for the order polynomial
May 5 Ehrhart polynomials and reciprocity in the plane; valuation property of lattice point counting; triangulations as posets; bookkeeping and Möbiusfunction; Polynomiality and recirocity of lattice triangles; Posets: order preserving maps and order ideals; (principal) order ideals; multichains of order ideals; Birkhoff lattice; the incidence algebra
April 29 (multi)subsets as special maps; partially ordered sets; examples: chain, antichain, boolean lattice, divisibility, ordered partition lattice; interval, cover relation, Hasse diagram, minimum/maximum; (strictly) order preserving maps; (strict) order polynomial; polynomiality; posets and acyclic orientations; chromatic polynomial as sum of order polynomials; (multi)subsets as lattice points in geometric objects; Ehrhart functions and Ehrhart-Macdonald reciprocity
April 22 flow on a graph with values in an abelian group; conservation of flow; nowhere-zero and flow polynomial; planar graphs and their duals; induced orientation; recovering colorings from differences on edges; dual to flow on dual; Tutte's 5-flow conjecture; totally cyclic orientations and combinatorial reciprocity for flow polynomials
April 14 What are combinatorial reciprocity theorems? subsets vs. multisubsets; graphs and colorings; chromatic polynomials; deletion-contraction operations; properties of chromatic polynomials; acyclic orientations; combinatorial reciprocity for chromatic polynomials


A solid background in linear algebra and some geometric intuition is sufficient but more mathematical background is surely welcome.