Abstract
We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovász local lemma in probabilistic combinatorics. We show that the conclusion of the Lovász local lemma holds for dependency graph G and probabilities {p x } if and only if the independent-set polynomial for G is nonvanishing in the polydisc of radii {p x }. Furthermore, we show that the usual proof of the Lovász local lemma – which provides a sufficient condition for this to occur – corresponds to a simple inductive argument for the nonvanishing of the independent-set polynomial in a polydisc, which was discovered implicitly by Shearer(98) and explicitly by Dobrushin.(37,38) We also present some refinements and extensions of both arguments, including a generalization of the Lovász local lemma that allows for ‘‘soft’’ dependencies. In addition, we prove some general properties of the partition function of a repulsive lattice gas, most of which are consequences of the alternating-sign property for the Mayer coefficients. We conclude with a brief discussion of the repulsive lattice gas on countably infinite graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Aigner (1979) Combinatorial, Grundlehren der mathematischen Wissenschaften #234 Springer-Verlag Berlin–New York
N. Alon J. Spencer (2000) The Probabilistic Method EditionNumber2 Wiley New York
N. Alon (1991) ArticleTitleA parallel algorithmic version of the local lemma Random Struct. Algorithms 2 367–378
J. L. Arocha (1984) ArticleTitlePropiedades del polinomio independiente de un grafo Revista Ciencias Matemáticas [Cuba] 5 103–110
R. Bamón J. Bobenrieth (1999) ArticleTitleThe rational maps z ↦ 1 + 1/ωzd have no Herman rings Proc. Am. Math. Soc. 127 633–636
R. J. Baxter (1981) ArticleTitleRogers–Ramanujan identities in the hard hexagon model J. Statist. Phys. 26 427–452
R. J. Baxter (1982) Exactly Solved Models in Statistical Mechanics Academic Press London–New York
J. Beck (1991) ArticleTitleAn algorithmic approach to the Lovász local lemma I Random Struct. Algorithms 2 343–365
J. Bellissard R. Høegh-Krohn (1982) ArticleTitleCompactness and the maximal Gibbs state for random Gibbs fields on a lattice Commun. Math. Phys. 84 297–327 Occurrence Handle83m:82002 Occurrence Handle0495.60057
S. Beraha J. Kahane N. J. Weiss (1978) Limits of zeroes of recursively defined families of polynomials, in Studies in Foundations and Combinatorics G.-C. Rota (Eds) Advances in Mathematics Supplementary Studies, Vol. 1 Academic Press New York 213–232
C. A. Berenstein R. Gay (1991) Complex Variables: An Introduction Springer-Verlag New York
J. Berg Particlevan den J. E. Steif (1994) ArticleTitlePercolation and the hard-core lattice gas model Stoch. Proc. Appl. 49 179–197
F. Bergeron G. Labelle P. Leroux (1998) Combinatorial Species and Tree-Like Structures Cambridge University Press Cambridge–New York
N. L. Biggs (1977) Interaction Models London Mathematical Society Lecture Note Series #30 Cambridge University Press Cambridge
N. Biggs (1993) Algebraic Graph Theory EditionNumber2 Cambridge University Press Cambridge– New York
P. Billingsley (1986) Probability and Measure EditionNumber2 Wiley New York
A. Björner (1992) The homology and shellability of matroids and geometric lattices, in Matroid Applications N. White (Eds) Encyclopedia of Mathematics and its Applications #40 Cambridge University Press Cambridge 226–283
J. R. Bobenrieth, Algunos aspectos de la dinámica de las funciones racionales z ↦ 1 + 1ωzd, Ph.D. thesis, Universidad de Chile (June 1997).
J. Bobenrieth (2001) ArticleTitleHyperbolicity is dense in the real family z ↦ 1 + 1ωzd (ω ∈ R), where d is odd Scientia, Ser. A, Math. Sci. (N.S.) 7 7–11
J. Bobenrieth (2002) ArticleTitleParabolic perturbation in the family z ↦ 1 + 1ωzd Proyecciones 21 1–7
J. Bobenrieth, Hyperbolic components of the family z ↦ 1 + 1ωzd, preprint (2000).
B. Bollobás (1998) Modern Graph Theory Springer-Verlag New York
B. Bollobás (2001) Random Graphs EditionNumber2 Cambridge University Press Cambridge
C. Borgs, Expansion Methods in Combinatorics, Conference Board of the Mathematical Sciences book series, preprint (2003), in press.
A. Bovier M. Zahradník (2000) ArticleTitleA simple inductive approach to the problem of convergence of cluster expansions of polymer models J. Statist. Phys. 100 765–778
G. R. Brightwell O. Häggström P. Winkler (1999) ArticleTitleNonmonotonic behavior in hard-core and Widom–Rowlinson models J. Statist. Phys. 94 415–435
J. I. Brown K. Dilcher R. J. Nowakowski (2000) ArticleTitleRoots of independence polynomials of well covered graphs J. Algebraic Combin. 11 197–210
J. I. Brown R. J. Nowakowski (2001) ArticleTitleBounding the roots of independence polynomials ARS Combin. 58 113–120
D. C. Brydges (1986) A short course on cluster expansions, in Phénomènes Critiques, Systèmes Aléatoires, Théories de Jauge/Critical Phenomena, Random Systems, Gauge Theories K. Osterwalder R. Stora (Eds) Les Houches summer school, Session XLIII, 1984 Elsevier/North-Holland Amsterdam 129–183
D. C. Brydges T. Kennedy (1987) ArticleTitleMayer expansions and the Hamilton–Jacobi equation J. Statist. Phys. 48 19–49
D. C. Brydges Ph. A. Martin (1999) ArticleTitleCoulomb systems at low density: A review J. Statist. Phys. 96 1163–1330
D. C. Brydges J. D. Wright (1988) ArticleTitleMayer expansions and the Hamilton–Jacobi equation. II. Fermions, dimensional reduction formulas. J. Statist. Phys. 51 435–456
C. Cammarota (1982) ArticleTitleDecay of correlations for infinite range interactions in unbounded spin systems Commun. Math. Phys. 85 517–528
Y.-B. Choe J. G. Oxley A. D. Sokal D. G. Wagner (2004) ArticleTitleHomogeneous multivariate polynomials with the half-plane property Adv. Appl. Math. 32 88–187
M. Chudnovsky and P. Seymour, The roots of the stable set polynomial of a claw-free graph, preprint (February 2004).
R. L. Dobrushin (1968) ArticleTitleThe problem of uniqueness of a Gibbs random field and the problem of phase transition Funct. Anal. Appl. 2 302–312
R. L. Dobrushin (1996) ArticleTitleEstimates of semi-invariants for the Ising model at low temperatures, in Topics in Statistical and Theoretical Physics American Mathematical Society Translations, Ser.2 177 59–81
R. L. Dobrushin (1996) Perturbation methods of the theory of Gibbsian fields, in Lectures on Probability Theory and Statistics P. Bernard (Eds) Ecole d’Eté de Probabilités de Saint-Flour XXIV – 1994, Lecture Notes in Mathematics #1648 Springer-Verlag Berlin, 1996 1–66
P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and finite sets, Vol. II, Colloq. Math. Soc. Janos Bolyai, Vol. 10 (North-Holland, Amsterdam, 1975), pp. 609–627.
P. Erdős J. Spencer (1991) ArticleTitleLopsided Lovász local lemma and Latin transversals Discrete Appl. Math. 30 151–154
D. C. Fisher J. M. Nonis (1990) ArticleTitleBounds on the ‘‘growth factor’’ of a graph Congr. Numer. 77 113–119
D. C. Fisher A. E. Solow (1990) ArticleTitleDependence polynomials Discrete Math. 82 251–258
D. Galvin J. Kahn (2004) ArticleTitleOn phase transition in the hard-core model on Zd Combin. Probab. Comput. 13 137–164
M. R. Garey D. S. Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman San Francisco
I. M. Gessel B. E. Sagan (1996) ArticleTitleThe Tutte polynomial of a graph, depth-first search, and simplicial complex partitions Electron. J. Combin. 3 IssueID2 #R9
J. Ginibre, On some recent work of Dobrushin, in Systèmes à un nombre infini de degrés de liberté, Colloques Internationaux du Centre National de la Recherche Scientifique, no. 181 (Éditions du Centre National de la Recherche Scientifique, Paris, 1970), pp. 163–175.
J. Glimm A. Jaffe (1987) Quantum Physics: A Functional Integral Point of View EditionNumber2 Springer-Verlag New York
J. Groeneveld (1962) ArticleTitleTwo theorems on classical many-particle systems Phys. Lett. 3 50–51
R. C. Gunning (1990) Introduction to Holomorphic Functions of Several Variables, Vol. I: Function Theory Wadsworth & Brooks/Cole Pacific Grove, California
W. Guo H. W. J. Blöte (2002) ArticleTitleFinite-size analysis of the hard-square lattice gas Phys. Rev. E 66 046140
I. Gutman (1991) ArticleTitleAn identity for the independence polynomials of trees Publ. Inst. Math. (Beograd) (N.S.) 50 IssueID64 19–23
I. Gutman (1992) ArticleTitleIndependent vertex sets in some compound graphs Publ. Inst. Math. (Beograd) (N.S.) 52 IssueID66 5–9
I. Gutman (1992) ArticleTitleSome analytical properties of the independence and matching polynomials Match 28 139–150
A. J. Guttmann (1987) ArticleTitleComment on ‘The exact location of partition function zeros, a new method for statistical mechanics’ J. Phys. A: Math. Gen. 20 511–512
O. Häggström (1997) ArticleTitleErgodicity of the hard-core model on Z2 with parity-dependent activities Ark. Mat. 35 171–184
Y. O. Hamidoune (1990) ArticleTitleOn the numbers of independent k-sets in a claw free graph J. Combin. Theory B 50 241–244
O. J. Heilmann (1974) ArticleTitleUse of reflection as symmetry operation in connection with Peierls argument Commun. Math. Phys. 36 91–114
O. J. Heilmann E. H. Lieb (1972) ArticleTitleTheory of monomer-dimer systems Commun. Math. Phys. 25 190–232
O. J. Heilmann E. Præstgaard (1973) ArticleTitlePhase transition of hard hexagons on a triangular lattice J. Stat. Phys. 9 23–44
O. J. Heilmann E. Præstgaard (1974) ArticleTitlePhase transition in a lattice gas with third nearest neighbour exclusion on a square lattice J. Phys. A: Math. Gen. 7 1913–1917
J. R. Heringa H. W. J. Blöte E. Luijten (2000) ArticleTitleHigh-dimensional lattice gases J. Phys. A: Math. Gen. 33 2929–2941
E. Hille (1973) Analytic Function Theory EditionNumber2 Chelsea New York
C. Hoede X.-L. Li (1994) ArticleTitleClique polynomials and independent set polynomials of graphs Discrete Math. 125 219–228
D. G. C. Horrocks (2002) ArticleTitleThe numbers of dependent k-sets in a graph are log concave J. Combin. Theory B 84 180–185
T. W. Hungerford (1974) Algebra Springer-Verlag New York
A. Iserles (1993) ArticleTitleOn the generalized pantograph functional–differential equation Eur. J. Appl. Math. 4 1–38
R. B. Israel (1979) Convexity in the Theory of Lattice Gases Princeton University Press Princeton NJ
S. Janson (1998) ArticleTitleNew versions of Suen’s correlation inequality Random Struct. Algorithms 13 467–483
J. Jonasson J. E. Steif (1999) ArticleTitleAmenability and phase transition in the Ising model J. Theoret. Probab. 12 549–559
J. Kahn (2001) ArticleTitleAn entropy approach to the hard-core model on bipartite graphs Combin. Probab. Comput. 10 219–237
J. Kahn (2002) ArticleTitleEntropy, independent sets and antichains: A new approach to Dedekind’s problem Proc. Am. Math. Soc. 130 371–378
R. Kotecký D. Preiss (1986) ArticleTitleCluster expansion for abstract polymer models Commun. Math. Phys. 103 491–498
S. G. Krantz (1992) Function Theory of Several Complex Variables EditionNumber2 Wadsworth & Brooks/Cole Pacific Grove, California
H. Künsch (1981) ArticleTitleAlmost sure entropy and the variational principle for random fields with unbounded state space Z. Wahrsch. verw. Gebiete 58 69–85
J. L. Lebowitz E. Presutti (1976) ArticleTitleStatistical mechanics of systems of unbounded spins Commun. Math. Phys. 50 195–218
B. Ja. Levin (1964) Distribution of Zeros of Entire Functions American Mathematical Society Providence
V. E. Levit and E. Mandrescu, On the roots of independence polynomials of almost all very well-covered graphs, preprint (2003), math.CO/0305227 at arXiv.org.
L. Lovász and M. D. Plummer, Matching Theory, North-Holland Mathematics Studies #121/Annals of Discrete Mathematics #29 (North-Holland, Amsterdam-New York/Akadémiai Kiadó, Budapest 1986).
W. S. Massey (1990) Algebraic Topology: An Introduction EditionNumber4 Springer-Verlag New York
C. Merino A. Mier Particlede M. Noy (2001) ArticleTitleIrreducibility of the Tutte polynomial of a connected matroid J. Combin. Theory B 83 298–304
J. Milnor (2000) ArticleTitleOn rational maps with two critical points Exp. Math. 9 481–522
S. Miracle-Solé (2000) ArticleTitleOn the convergence of cluster expansions Physica A 279 244–249
M. Molloy B. Reed (2002) Graph Colouring and the Probabilistic Method Springer-Verlag Berlin-New York
P. Montel (1927) Leçons sur les familles normales de fonctions analytiques et leurs applications Gauthier-Villars Paris
G. R. Morris, A. Feldstein and E. W. Bowen, The Phragmén–Lindelöf principle and a class of functional differential equations, in Ordinary Differential Equations: 1971 NRL-MRC Conference, L. Weiss, ed. (Academic Press, New York, 1972), pp. 513–540.
J. G. Oxley (1992) Matroid Theory Oxford University Press New York
O. Penrose (1963) ArticleTitleConvergence of fugacity expansions for fluids and lattice gases J. Math. Phys. 4 1312–1320
O. Penrose, Convergence of fugacity expansions for classical systems, in Statistical Mechanics: Foundations and Applications, T. A. Bak, ed. (Benjamin, New York–Amsterdam, 1967), PP. 101–109.
A. Procacci B. N. B. Lima Particlede B. Scoppola (1998) ArticleTitleA remark on high temperature polymer expansion for lattice systems with infinite range pair interactions Lett. Math. Phys. 45 303–322
A. Procacci B. Scoppola (1999) ArticleTitlePolymer gas approach to N-body lattice systems J. Statist. Phys. 96 49–68
A. Procacci B. Scoppola V. Gerasimov (2003) ArticleTitlePotts model on infinite graphs and the limit of chromatic polynomials Commun. Math. Phys. 235 215–231
R. M. Range (1986) Holomorphic Functions and Integral Representations in Several Complex Variables Springer-Verlag New York
D. Ruelle (1976) ArticleTitleProbability estimates for continuous spin systems Commun. Math. Phys. 50 189–194
L. K. Runnels (1967) ArticleTitlePhase transition of a Bethe lattice gas of hard molecules J. Math. Phys. 10 2081–2087
L. K. Runnels (1975) ArticleTitlePhase transitions of hard sphere lattice gases Commun. Math. Phys. 40 37–48
J. L. Schiff (1993) Normal Families Springer-Verlag New York
E. G. Seiler (1982) Gauge Theories as a Problem of Constructive Quantum Field Theory and Statistical Mechanics, Lecture Notes in Physics #159 Springer-Verlag Berlin–New York
J. B. Shearer (1985) ArticleTitleOn a problem of Spencer Combinatorica 5 241–245
B. Simon (1974) The P(φ)2 Euclidean (Quantum) Field Theory Princeton University Press Princeton NJ
B. Simon (1993) The Statistical Mechanics of Lattice Gases Princeton University Press Princeton NJ
A. D. Sokal (2001) ArticleTitleBounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions Combin. Probab. Comput. 10 41–77
A. D. Sokal (2001) ArticleTitleA personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models, Markov Process Related Fields 7 21–38
A. D. Sokal (2004) ArticleTitleChromatic roots are dense in the whole complex plane Combin. Probab. Comput. 13 221–261 Occurrence Handle10.1017/S0963548303006023
A. D. Sokal, Tree limit of Mayer expansion, in preparation.
J. Spencer (1975) ArticleTitleRamsey’s Theorem – a new lower bound J. Comb. Theory A 18 108–115
J. Spencer (1977/78) ArticleTitleAsymptotic lower bounds for Ramsey functions Discrete Math. 20 69–76
R. P. Stanley (1986) Enumerative Combinatorics, Vol. 1 Wadsworth & Brooks/Cole Monterey, California
R. P. Stanley (1999) Enumerative Combinatorics, Vol. 2 Cambridge University Press Cambridge–New York
W. C. Suen (1990) ArticleTitleA correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph Random Struct. Algorithms 1 231–242
S. Todo (1999) ArticleTitleTransfer-matrix study of negative-fugacity singularity of hard-core lattice gas Int. J. Mod. Phys. C 10 517–529
S. Todo, private communication (August 2003).
G. E. Uhlenbeck and G. W. Ford, The theory of linear graphs with applications to the theory of the virial development of the properties of gases, in Studies in Statistical Mechanics, Vol. I, J. de Boer and G. E. Uhlenbeck, eds. (North-Holland, Amsterdam, 1962), PP. 119–211.
A. C. D. Enter Particlevan R. Fernández A. D. Sokal (1993) ArticleTitleRegularity properties and pathologies of position-space renormalization-group transformations: Scope and limitations of Gibbsian theory J. Statist. Phys. 72 879–1167
V. S. Vladimirov (1966) Methods of the Theory of Functions of Many Complex Variables MIT Press Cambridge, MA
H. S. Wilf (1994) generatingfunctionology EditionNumber2 Academic Press San Diego–London
D. Williams (1991) Probability with Martingales Cambridge University Press Cambridge
G. M. Ziegler (1995) Lectures on Polytopes Springer-Verlag New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Scott, A.D., Sokal, A.D. The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lovász Local Lemma. J Stat Phys 118, 1151–1261 (2005). https://doi.org/10.1007/s10955-004-2055-4
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10955-004-2055-4