Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 7 (2010) open journal systems 

Combinatorics and cluster expansions

William G. Faris, University of Arizona

This article is about the connection between enumerative combinatorics and equilibrium statistical mechanics. The combinatorics side concerns species of combinatorial structures and the associated exponential generating functions. The passage from species to generating functions is a combinatorial analog of the Fourier transform. Indeed, there is a convolution multiplication on species that is mapped to a pointwise multiplication of the exponential generating functions. The statistical mechanics side deals with a probability model of an equilibrium gas. The cluster expansion that gives the density of the gas is the exponential generating function for the species of rooted connected graphs. The main results of the theory are simple criteria that guarantee the convergence of this expansion. It turns out that other problems in combinatorics and statistical mechanics can be translated to this gas setting, so it is a universal prescription for dealing with systems of high dimension.

AMS 2000 subject classifications: Primary 82B20, 60K35; secondary 82B05, 05C30, 05A15.

Keywords: Equilibrium lattice gas, polymer system, cluster expansion, species of structures, exponential generating function, connected graph.

Creative Common LOGO

Full Text: PDF

Faris, William G., Combinatorics and cluster expansions, Probability Surveys, 7, (2010), 157-206 (electronic). DOI: 10.1214/10-PS159.


[1]   Abdelmalek Abdesselam and Vincent Rivasseau, Trees, forests, and jungles: A botanical garden for cluster expansions, pp. 7–36 in Constructive Physics: Results in Field Theory, Statistical Mechanics and Condensed Matter Physics, Proceedings of the Conference Held at Ecole Polytechnique, Palaiseau, France, 25–27 July, 1994, (Lecture Notes in Physics 446), ed. by Vincent Rivasseau, Springer, Berlin, 1995. MR1356024

[2]   François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, Cambridge, 1998. MR1629341

[3]   Anders Björner, The homology and shellability of matroids and geometric lattices, Chapter 7, pp. 226–283 in Matroid Applications, (Encyclopedia of Mathematics and its Applications 40), ed. by Neil White, Cambridge University Press, Cambridge, 1992. MR1165544

[4]   Anton Bovier and Miloš Zahradník, A simple inductive approach to the problem of convergence of cluster expansions of polymers, J. Stat. Phys. 100 (2000), pp. 765–778. MR1788485

[5]   David C. Brydges, A short course on cluster expansions, Course 3, pp. 129–183 in Critical Phenomena, Random Systems, Gauge Theories, Les Houches, Session XLIII, 1984, Part I, ed. by K. Osterwalder and R. Stora, Elsevier, Amsterdam, 1986. MR0880525

[6]   David C. Brydges, Functional Integrals and their Applications (Notes for a course for the Troisieme Cycle de la Physique en Suisse Romande given in Lausanne, Switzerland, during the summer of 1992). Notes with the collaboration of R. Fernandez.

[7]   David C. Brydges and Thomas G. Kennedy, Mayer expansions and the Hamilton-Jacobi Equation, J. Stat. Phys. 48 (1987), 19–49. MR0914427

[8]   David C. Brydges and Philippe A. Martin, Coulomb systems at low density: A review, J. Stat. Phys. 96 (1999), 1163–1330. MR1722991

[9]   Roland L. Dobrushin, Perturbation methods of the theory of Gibbsian fields, pp. 1–66 in Lectures on Probability Theory and Statistics, Ecole d’été de probabilités de Saint-Flour (24th 1994), (Lectures Notes in Math. 1648), ed. by P. Bernard, Springer-Verlag, Berlin, 1996. MR1600880

[10]   William G. Faris, A gentle introduction to cluster expansions, pp. 97–115 in Probability and Partial Differential Equations in Modern Applied Mathematics, (IMA Volumes in Mathematics and its Applications 140), ed. by Edward C. Waymire and Jinqiao Duan, Springer, New York, 2005. MR2202035

[11]   William G. Faris, A connected graph identity and convergence of cluster expansions, J. Math. Phys. 49, 113302 (2008). MR2468534

[12]   William G. Faris and Robert A. Minlos, A quantum crystal with multidimensional harmonic oscillators, J. Stat. Phys. 94 (1999), pp. 365–387. MR1675357

[13]   Roberto Fernández and Aldo Procacci, Cluster expansion for abstract polymer models. New bounds from an old approach, Commun. Math. Phys. 274 (2007), 123–140. MR2318850

[14]   Roman Kotecký and David Preiss, Cluster expansion for abstract polymer models, Commun. Math. Phys. 103 (1986), 491–498. MR0832923

[15]   Pierre Leroux, Enumerative problems inspired by Mayer’s theory of cluster integrals, Electron. J. Combin. 11(1) (2004), [R32]. MR2056084

[16]   Vadim A. Malyshev and Robert A. Minlos, Gibbs Random Fields: Cluster Expansions, Kluwer, Dordrecht, 1991. MR1191166

[17]   Salvador Miracle-Sole, On the convergence of cluster expansions, Physica A 279 (2000), pp. 244–249. MR1797141

[18]   Oliver Penrose, Convergence of fugacity expansions for classical systems, pp. 101–109 in Statistical Mechanics: Foundations and Applications: Proceedings of the I.U.P.A.P. meeting, Copenhagen, 1966, ed. by Thor A. Bak, W.A. Benjamin, New York, 1967.

[19]   Suren Poghosyan and Daniel Ueltschi, Abstract cluster expansion with applications to statistical mechanical systems, J. Math. Phys. 50, 053509 (2009). MR2531305

[20]   Aldo Procacci, Abstract polymer models with general pair interactions, J. Stat. Phys. 129 (2007), 171–188. MR2349524

[21]   Alexander D. Scott and Alan D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys. 118, 1151–1261. MR2130890

[22]   Daniel Ueltschi, Cluster expansions and correlation functions, Moscow Math. J. 4 (2004), 509–520. MR2108447

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787