Spring 2005: Enumerative Combinatorics
Abstracts for the lectures:
- Martin Aigner (Freie Universität Berlin):
Lattice Paths and Determinants
The Lemma of Gessel-Viennot relating determinants to the enumeration of
weighted lattice paths has become an instant classic in enumerative
combinatorics. We introduce and prove the Lemma, discuss its importance in
matrix theory, and look then at a number of applications including
Catalan paths, Stirling numbers, binomial determinants, and more advanced
topics such as orthogonal polynomials and Hankel matrices.
- Martin Loebl (Charles University Prague) :
Discrete Tools in the Theory of the Ising Problem
The Ising Model is one of basic constructions of theoretical physics.
I would like to explain some beautiful discrete constructions
which belong to its rich mathematics. The lecture will start with
a simple introduction of the Ising problem, basic graph theory of
edge-cuts and a quick introduction to the chromatic and Tutte polynomials.
Then come the dualities (at least two) and the theory of Pfaffian
orientations (an example of a statement from this theory: The permanent
of a matrix A may be written as a linear combination of the determinants
of matrices obtained from A by changing signs.) Then I explain
the infinite product formula of Feynman and Sherman (for 2D Ising
partition function). It is closely related to the Witt formula.
These considerations naturally lead to the Ihara-Selberg zeta function
of a graph, McMahon´s theorem and its recently proved q-version.
Some more curious q-observations may follow, if time allows.
- Marc Noy
(Univ. Politécnica de Catalunya):
Enumerative combinatorics: a symbolic and analytic approach
We show how the 'symbolic method' allows for a unified treatment of
many problems in enumerative combinatorics. The main object
of study in this approach are generating functions. Set-theoretical
constructions on combinatorial structures translate into algebraic
operations on the corresponding generating functions. The next step
is to analyze, and eventually solve, the functional/differential equations
In a second part, we show how to use methods of complex analysis
for obtaining asymptotic estimates of counting sequences. The key is to
consider generating functions as complex functions and to study their
behavior near their main singularities. This is the essence of the method
known as 'singularity analysis', which provides general theorems that
can be apply to a wealth of combinatorial structures.
The basic reference for this lecture is the forthcoming book
'Analytic Combinatorics' by P. Flajolet and R. Sedgewick
- Richard Stanley
(Massachusetts Institute of Technology):
An introduction to the RSK algorithm
The RSK algorithm (named after G. de B. Robinson,
C. Schensted, and D. Knuth) is perhaps the most interesting
combinatorial algorithm in all of mathematics. It gives a bijection
between permutations and certain pairs of standard Young tableaux
(SYT), and has many applications to combinatorics and representation
theory. We will discuss the basic combinatorial properties of SYT and
the RSK algorithm, including the Frame-Robinson-Thrall hook length
formula and the remarkable symmetry properties of RSK. Applications
will be given to plane partitions, increasing and decreasing sequences
of permutations, and reduced decompositions of permutations.