[home] - [up]

 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 that arise.

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.

 [home] - [up] - [top] Last modified: Thu Jan 27 18:53:51 CET 2005