Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T14:02:55.102Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Widom–Rowlinson Occupancy Fraction in Regular Graphs

Part of: Graph theory Equilibrium statistical mechanics

Published online by Cambridge University Press:  09 August 2016

EMMA COHEN ,
WILL PERKINS  and
PRASAD TETALI
EMMA COHEN
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA (e-mail: ecohen32@gatech.edu, tetali@math.gatech.edu)
WILL PERKINS
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: math@willperkins.org)
PRASAD TETALI
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA (e-mail: ecohen32@gatech.edu, tetali@math.gatech.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the Widom–Rowlinson model of two types of interacting particles on d-regular graphs. We prove a tight upper bound on the occupancy fraction, the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on d + 1 vertices, K d+1. As a corollary we find that K d+1 also maximizes the normalized partition function of the Widom–Rowlinson model over the class of d-regular graphs. A special case of this shows that the normalized number of homomorphisms from any d-regular graph G to the graph HWR , a path on three vertices with a loop on each vertex, is maximized by K d+1. This proves a conjecture of Galvin.

MSC classification

Primary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Secondary: 05C35: Extremal problems 82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 183 - 194
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Brightwell, G. and Winkler, P. (2002) Hard constraints and the Bethe lattice: Adventures at the interface of combinatorics and statistical physics. In Proc. International Congress of Mathematicians, Vol. III, pp. 605–624.Google Scholar
[2] Chayes, J., Chayes, L. and Kotecky, R. (1995) The analysis of the Widom–Rowlinson model by stochastic geometric methods. Comm. Math. Phys. 172 551–569.Google Scholar
[3] Davies, E., Jenssen, M., Perkins, W. and Roberts, B. (2015) Independent sets, matchings, and occupancy fractions. arXiv:1508.04675 Google Scholar
[4] Dembo, A., Montanari, A., Sun, N., et al. (2013) Factor models on locally tree-like graphs. Ann. Probab. 41 4162–4213.CrossRefGoogle Scholar
[5] Galvin, D. (2013) Maximizing H-colorings of a regular graph. J. Graph Theory 73 66–84.Google Scholar
[6] Galvin, D. (2014) Three tutorial lectures on entropy and counting. arXiv:1406.7872 Google Scholar
[7] Galvin, D. and Tetali, P. (2004) On weighted graph homomorphisms. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 63, pp. 97–104.Google Scholar
[8] Kahn, J. (2001) An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10 219–237.CrossRefGoogle Scholar
[9] Lebowitz, J. and Gallavotti, G. (1971) Phase transitions in binary lattice gases. J. Math. Phys. 12 1129–1133.Google Scholar
[10] Radhakrishnan, J. (2003) Entropy and counting. In Computational Mathematics, Modelling and Algorithms (Mishra, J. C., ed), Vol. 146, Narosa Publishers.Google Scholar
[11] Ruelle, D. (1971) Existence of a phase transition in a continuous classical system. Phys. Rev. Lett. 27 1040.Google Scholar
[12] Sernau, L. (2015) Graph operations and upper bounds on graph homomorphism counts. arXiv:1510.01833 Google Scholar
[13] Widom, B. and Rowlinson, J. S. (1970) New model for the study of liquid–vapor phase transitions. J. Chem. Phys. 52 1670–1684.Google Scholar
[14] Zhao, Y. (2010) The number of independent sets in a regular graph. Combin. Probab. Comput. 19 315–320.Google Scholar
[15] Zhao, Y. (2011) The bipartite swapping trick on graph homomorphisms. SIAM J. Discrete Math. 25 660–680.CrossRefGoogle Scholar