| lecture | monday 8:30-10:00 | Arnimallee 6 SR 025/026 |
| recitation | thursday 10:15-11:45 | Arnimallee 3 SR 119 |
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 Mathematik III".
| [B1] | Matthias Beck, Combinatorial reciprocity theorems, Book draft, 2011 |
| [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 |
| Homework #5 | due Feb 16 |
| Homework #4 | due Dec 15 |
| Homework #3 | due Dec 5 |
| Homework #2 | due Nov 17 |
| Homework #1 | due |
| Feb 06 |
Graph colorings/flows geometrically; proper colorings are
lattice points in open cubes not on the graphical arrangement;
graphical arrangement subdivides cube into order polytopes Z_k-flows: in-coming flow minus out-going flow is a multiple of k; nowhere zero Z_k-flows are lattice points in finitely many sections of the cube |
| Jan 30 | P-partition of n: order preserving map from finite poset P into natural numbers such that sum of image is n; P interpolates between chain and anti-chain; P-partitions interpolate between partitions and compositions; correspond to lattice points in a cone; decomposition of cone into simplicial cones corresponding to linear extensions; canonical (irrational) decomposition of the cone using permutation statistics; rational generating functions and reciprocity related to classical notions such as descent sets, major index and inversion statistics |
| Jan 23 | Order polytopes: Order preserving maps from P into [0,1]; Ehrhart function yields order polynomial and reciprocity; canonical triangulation into unimodular simplices along (strict) chains of order ideals; gives geometric intuition for combinatorial proof that we did Nov 14 |
| Jan 16 | Ehrhart theory for general rational polytopes via (regular) subdivisions; Ehrhart-Macdonald reciprocity via Möbius functions |
| Jan 09 |
Regular subdivisions and their Möbius functions
(continued) Ehrhart theory for simplices; half-open parallelepipeds and rational generating functions; Ehrhart-Macdonald reciprocity via generating function reciprocity |
| Jan 05 |
Möbius function of face posets of polyhedron via Euler
characteristics; filters in face poset is face figure of
polyhedron; intervals are again face posets polyhedral complexes and subdivisions of polyhedra; regular subdivisions |
| Dec 12 | Cubes, simplices, f-vectors, Euler characteristic; Theorem: The Euler characteristic of a pointed polyhedron is 1 (bounded) or 0 (unbounded). |
| Dec 5 | Convex bodies/sets: polyhedra, polytopes, (polyhedral) cones; operations: sections, projections, Minkowski sums; Minkowski-Weyl theorem; Boundary structure: faces of convex bodies (intrinsic), supporting hyperplanes, faces of polyhedra (extrinsic), face of a face is a face, dimension of faces (k-face), face lattice, examples |
| Nov 28 | quasi-polynomials, examples: quasi-polynomials from restricted partitions, Ehrhart functions for rational segments, characterization of quasi-polynomials, reciprocity for rational generating functions, information from the numerator polynomial, combinatorial reciprocity for restricted partitions |
| Nov 21 | entries in matrix powers as counting functions, rational generating functions, example: (multi)subsets, restricted partitions, characterization of rational generating functions, polynomials, application to matrix powers |
| Nov 14 |
Reciprocity for order polynomials -- combinatorially (at
first) o.p. maps to an n-chain and chains of order ideals, Birkhoff construction for distributive lattices, order polynomial as evaluations of the zeta function, Möbius function for J(Q), the (weak) Crosscut Theorem in the Möbius algebra |
| Nov 7 |
Ehrhart theory in the plane: the Ehrhart function of a
latticep polygon is a polynomial, Ehrhart-Macdonald
reciprocity, Pick's theorem. Proofs via (special) triangles
and triangulations incidence algebra, zeta function, invertible elements, Möbius function, Möbius inversion formula |
| Oct 31 |
from (multi)subsets to order polynomials, posets, Hasse
diagrams, counting (strictly) order preserving maps into
chains, chromatic polynomials as sums of strict order
polynomials from (multi)subsets to counting lattice points in triangles, reciprocity translated: lattice points in the interior vs. in the whole triangle |
| Oct 20 | flows in graphs, nowhere zero H-flows, flow reciprocity (generalized) Tutte-Grothendieck invariants, Tutte polynomials |
| Oct 17 | what is a combinatorial reciprocity Example: subset-multisubset-reciprocity Graph colorings: chromatic polynomials at negative integers |