On the Widom-Rowlinson occupancy fraction in regular graphs

Research output: Contribution to journalArticlepeer-review

Standard

On the Widom-Rowlinson occupancy fraction in regular graphs. / Cohen, Emma; Perkins, Will; Tetali, Prasad.

In: Combinatorics, Probability and Computing, 09.08.2016.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{5d946e63f1fc454d9e02c99c06f2c67f,
title = "On the Widom-Rowlinson occupancy fraction in regular graphs",
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.",
author = "Emma Cohen and Will Perkins and Prasad Tetali",
year = "2016",
month = aug,
day = "9",
doi = "10.1017/S0963548316000249",
language = "English",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",

}

RIS

TY - JOUR

T1 - On the Widom-Rowlinson occupancy fraction in regular graphs

AU - Cohen, Emma

AU - Perkins, Will

AU - Tetali, Prasad

PY - 2016/8/9

Y1 - 2016/8/9

N2 - 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.

AB - 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.

U2 - 10.1017/S0963548316000249

DO - 10.1017/S0963548316000249

M3 - Article

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

ER -