Exposés : 1, 2, 3, 4

Exercices

1. 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).
   
   
2. 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.
   
   
3. If time permits, another walk model involving surface interactions.
   

Exposé

Exercices

1. 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.
   
2. 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.
3. 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)

Exposé

Exercices

1. 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.


• q-series, q-calculus, q-analogues


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.
2. 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.

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
- 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

C3. Others...

C4. Some hot (and mysterious) topics: self-avoiding walks,
alternating sign matrices, tilings, meanders...

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

b. Duality

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