On the Widom-Rowlinson occupancy fraction in regular graphs

ACO Student Seminar
Friday, February 5, 2016 - 13:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
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.  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, proving a conjecture of Galvin. Joint work with Will Perkins and Prasad Tetali.