On the Widom-Rowlinson occupancy fraction in regular graphs

Emma Cohen, Will Perkins, Prasad Tetali

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
189 Downloads (Pure)

Abstract

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, Kd+1. As a corollary we find that Kd+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 Kd+1. This proves a conjecture of Galvin.
Original languageEnglish
JournalCombinatorics, Probability and Computing
Early online date9 Aug 2016
DOIs
Publication statusE-pub ahead of print - 9 Aug 2016

Fingerprint

Dive into the research topics of 'On the Widom-Rowlinson occupancy fraction in regular graphs'. Together they form a unique fingerprint.

Cite this