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