|Tony Guttmann (University of Melbourne)
An introduction to Statistical mechanics for combinatorialists (3 hours)
Exposés : 1, 2, 3, 4
- 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. (1-1.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 self-avoiding 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 hours)
- 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. Hard-core continuous gaz in one dimension. Explicit examples and tables.
Xavier Viennot (LaBRI, Bordeaux, France)
Enumerative Combinatorics and Physics (3 hours)
- 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),• q-series, q-calculus, q-analogues
Example: Dyck paths with bounded height, Fibonacci polynomials and matchings.
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 Ambjorn-Loll and Di Francesco-Guitter-Kristianjen), general triangulations and connected heaps of dimers (Bousquet-Mélou, Rechnitzer).
• q-Bessel functions in statistical physics
Solid-on-solid model (SOS paths),
Staircase polygons (parallelogram polyominos with perimeter and area),
combinatorial interpretation of q-Bessel functions and heaps of segments.
• Gas model, Hard hexagons combinatorial interpretation of the thermodynamic limit,
interpretation of the gas density with pyramids.
|Mireille Bousquet-Mélou (CNRS, LaBRI, Université Bordeaux 1, France)
Asymptotic Enumeration and Large Random Objects
Exposés: 1, 2, 3
A. Why asymptotics?
A1. When exact enumeration is out of reach:
- some very hard problems
A2. When exact results are available, asymptotic results
- 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
- D-finite generating functions
B4. Software for automatic asymptotics
B5. What to read, where to learn
C. Examples of asymptotic counting and limit laws
C1. Two-dimensional 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
C4. Some hot (and mysterious) topics: self-avoiding walks,
alternating sign matrices, tilings, meanders...
|Alan Sokal (New York University)
Tutte polynomials and statistical mechanics (3 hours)
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 on-line 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 Fortuin-Kasteleyn identity relating them (and remark on the random-cluster model)
b. Special cases: Chromatic polynomial, flow polynomial, $q \to 0$ limits (reliability polynomial, spanning-forest polynomial, spanning-tree 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
c. Deletion-contraction identity
d. Parallel-reduction and series-reduction identities
e. Reduction formulae for 2-rooted subgraphs
f. Analogy with electrical circuit theory
3. Real and complex zeros of the multivariate Tutte polynomial: Why should we care?
a. Yang-Lee approach to phase transitions
b. Theorems of Lee-Yang type ("soft" and "hard")
4. Spanning trees, electric circuits, and all that
a. The matrix-tree theorem and its variants
b. Electric circuits and the half-plane property for graphs
c. The half-plane property for matroids
d. Electric circuits and the Rayleigh property for graphs
e. The Rayleigh property for matroids
5. The reliability polynomial
a. The Brown-Colbourn property for graphs
b. The Brown-Colbourn property for matroids
6. Spanning forests and the Grassmann-integral 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