Theme semester in recent advances in combinatorics

## School Statistical Mechanics and Combinatorics

#### February 12-16, 2007

francais
##### SCIENTIFIC ORGANIZERS Mireille Bousquet-Mélou (Bordeaux) Tony Guttmann (Melbourne)Pierre Leroux (UQAM) Alan Sokal (New York)

 Participants Schedule

 PROGRAMME Tony Guttmann (University of Melbourne) An introduction to Statistical mechanics for combinatorialists (3 hours) 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. (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) 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. Hard-core continuous gaz in one dimension. Explicit examples and tables. Xavier Viennot (LaBRI, Bordeaux, France) Enumerative Combinatorics and Physics (3 hours) 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.• 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. 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 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... 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 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