PROGRAMME



Tony Guttmann (University of Melbourne)
An Introduction to Statistical Mechanics for Combinatorialists (3 heures)
Exposés : 1, 2, 3, 4
Exercices
 A rapid history of statistical mechanics, from Clasius,
via Maxwell, Boltzmann to Gibbs. Finishing with the canonical
ensemble partition function, and making connections with the
generating function familiar to people working with combinatorial
models. (11.5 lectures).
 The Ising model as a model in statistical mechanics, its
graphical interpretation as a combinatorial model. The generalisation
of the Ising model to the O(N) model, and the N > 0 limit,
yielding the selfavoiding walk model.
 If time permits, another walk model involving surface interactions.


Gilbert Labelle (UQAM)
Combinatorial Species, Labelled and Unlabelled Enumeration and Mayer Graph Weights
(3 heures)
Exposé
Exercices
 Elementary introduction to species through examples : Collecting structures into species leading to the general definition of a combinatorial species. Exponential generating series of a species for labelled enumeration. Elementary combinatorial operations between species. Explicit examples.
 More advanced theory : Cycle index and tilda series of a species for unlabelled enumeration Equipotence versus combinatorial equality. Combinatorial functional equations. Taking connected components. Iterative computational methods.
 Mayer’s graph weights : Short review of Mayer’s theory of cluster integrals. First and second Mayer’s weights W(g) and w(c). Sufficient integrability conditions for the existence of the thermodynamical limit w(c). Combinatorial functional equations for weighted connected graphs. Gaussian potentials. Hardcore continuous gaz in one dimension. Explicit examples and tables.


Xavier Viennot (LaBRI, Bordeaux, France)
Enumerative Combinatorics and Physics (3 heures)
Exposé
Exercices
 Basic enumerative combinatorics
• Binary tree, Catalan numbers, recurrence relations
• Generating functions, formal power series
Example: Catalan number, algebra of formal power series, Fibonacci numbers, algebraic equation for Catalan numbers.
• Bijective combinatorics, example with Catalan numbers
• Algebricity, decomposable structures. Example: rooted planar maps, balanced blossoming trees.
• Substitution in generating function.
Example: Strahler number of binary trees, logarithmic height of Dyck paths.
• Rational generating functions
Inversion formula with weighted paths (or transition matrix methodology), Example: Dyck paths with bounded height, Fibonacci polynomials and matchings.
• qseries, qcalculus, qanalogues
Partitions of integers, Ferrers diagrams. • Bijective proof of an identity, the bijective paradigm
• Algebraic combinatorics: an example with commutations and heaps of pieces commutations monoids and heaps of dimers, inversion formula: generating function for heaps of pieces, extensions with maximal pieces and pyramids.
 Applications and interactions with physics
• The directed animal model • Commutations and heaps of pieces: 3 basic lemma:
inversion lemma and extension (see lesson 1), logarithmic lemma, the “push operator”, path = heap. • application: generating function for directed animals (square and triangular lattice),
Motzkin paths. Random directed animals.
• Lorentzian triangulations in 2D quantum gravity bijection between Lorentzian triangulations and heaps of dimers, border conditions of AmbjornLoll and Di FrancescoGuitterKristianjen), general triangulations and connected heaps of dimers (BousquetMélou, Rechnitzer).
• qBessel functions in statistical physics
Solidonsolid model (SOS paths),
Staircase polygons (parallelogram polyominos with perimeter and area),
combinatorial interpretation of qBessel functions and heaps of segments.
• Gas model, Hard hexagons combinatorial interpretation of the thermodynamic limit,
interpretation of the gas density with pyramids.


Mireille BousquetMélou (CNRS, LaBRI, Université Bordeaux 1, France)
Asymptotic Enumeration and Large Random Objects
Exposés: 1, 2, 3
Exercices
A. Why asymptotics?
A1. When exact enumeration is out of reach:
 some very hard problems
A2. When exact results are available, asymptotic results
remain valuable:
 comparing classes of objects
 applications to random generation
 large random objects, limit phenomena, limit laws
 phase transitions
B. Techniques for asymptotics
B1. Asymptotics of sums
B2. Starting from generating functions:
 Flajolet and Odlyzko "singularity analysis"
 saddle point methods, etc.
B3. Systematic results:
 algebraic generating functions
 Dfinite generating functions
B4. Software for automatic asymptotics
B5. What to read, where to learn
C. Examples of asymptotic counting and limit laws
C1. Twodimensional lattice paths in a wedge: exact and asymptotic results
C2. A phase transition for polymers at an interface and/or for vesicles
in a solvent
C3. Others...
C4. Some hot (and mysterious) topics: selfavoiding walks,
alternating sign matrices, tilings, meanders...


Alan Sokal (New York University)
Tutte polynomials and statistical mechanics (3 heures)
These lectures are based on my review article "The multivariate Tutte polynomial (alias Potts model) for graphs and matroids", published in the proceedings of the 2005 British Combinatorial Conference and available online at http://arxiv.org/abs/math.CO/0503607
1. The multivariate Tutte polynomial, the Potts model, and all that
a. The multivariate Tutte polynomial for graphs, the Potts model in statistical mechanics, and the FortuinKasteleyn identity relating them (and remark on the randomcluster model)
b. Special cases: Chromatic polynomial, flow polynomial, $q \to 0$ limits (reliability polynomial, spanningforest polynomial, spanningtree polynomial)
c. Comparison to the standard Tutte polynomial
d. Very brief introduction to matroid theory; the multivariate Tutte polynomial for matroids
2. Identities for the multivariate Tutte polynomial
a. Disjoint unions and direct sums
b. Duality
c. Deletioncontraction identity
d. Parallelreduction and seriesreduction identities
e. Reduction formulae for 2rooted subgraphs
f. Analogy with electrical circuit theory
3. Real and complex zeros of the multivariate Tutte polynomial: Why should we care?
a. YangLee approach to phase transitions
b. Theorems of LeeYang type ("soft" and "hard")
4. Spanning trees, electric circuits, and all that
a. The matrixtree theorem and its variants
b. Electric circuits and the halfplane property for graphs
c. The halfplane property for matroids
d. Electric circuits and the Rayleigh property for graphs
e. The Rayleigh property for matroids
5. The reliability polynomial
a. The BrownColbourn property for graphs
b. The BrownColbourn property for matroids
6. Spanning forests and the Grassmannintegral representation
7. Complex zeros of the chromatic polynomial
a. Chromatic roots are dense in the whole complex plane
b. Bounds in terms of maximum degree and its relatives
c. Bounds in terms of maxmaxflow?
d. Open questions

