The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph

Let H-wR be the path on 3 vertices with a loop at each vertex. D. Galvin (Galvin, 2013, 2014) conjectured, and E. Cohen, W. Perkins and P. Tetali (Cohen et al., in press) proved that for any d -regular simple graph G on n vertices we have hom(G, H-wR) <= hom(Kd+1, H-wR)(n/(d+1)). In this paper we give a short proof of this theorem together with the proof of a conjecture of Cohen, Perkins and Tetali (Cohen et al., in press). Our main tool is a simple bijection between the Widom-Rowlinson model and the hard-core model on another graph. We also give a large class of graphs H for which we have hom(G, H) <= hom(Kd+1,H)(n/(d+1)). In particular, we show that the above inequality holds if H is a path or a cycle of even length at least 6 with loops at every vertex. (C) 2016 Elsevier Ltd. All rights reserved.