On the Widom-Rowlinson occupancy fraction in regular graphs

DOI10.1017/S0963548316000249MaRDI QIDQ5366940zbMATH OpenOpenAlexFDO

Authors Emma Cohen, Will Perkins, Prasad Tetali

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06398

zbMATH Keywords

Widom-Rowlinson model\(d\)-regular graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

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, $K_{d+1}$'s. As a corollary we find that $K_{d+1}$ also maximises the normalised partition function of the Widom-Rowlinson model over the class of d-regular graphs. A special case of this shows that the normalised number of homomorphisms from any d-regular graph $G$ to the graph $H_{WR}$, a path on three vertices with a loop on each vertex, is maximised by $K_{d+1}$. This proves a conjecture of Galvin.

Recommendations

• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• Independent sets, matchings, and occupancy fractions
• Graph operations and upper bounds on graph homomorphism counts
• Counting colorings of a regular graph
• A reverse Sidorenko inequality

Cites work

• scientific article; zbMATH DE number 1789918 (Why is no real title available?)
• An entropy approach to the hard-core model on bipartite graphs
• Factor models on locally tree-like graphs
• Graph operations and upper bounds on graph homomorphism counts
• Independent sets, matchings, and occupancy fractions
• Maximizing \(H\)-colorings of a regular graph
• On weighted graph homomorphisms
• The analysis of the Widom-Rowlinson model by stochastic geometric methods
• The bipartite swapping trick on graph homomorphisms
• The number of independent sets in a regular graph

Cited in

(12)

• Extremal regular graphs: independent sets and graph homomorphisms
• Counting proper colourings in 4-regular graphs via the Potts model
• Low-temperature behavior of the multicomponent Widom-Rowlison model on finite square lattices
• Graph operations and upper bounds on graph homomorphism counts
• On the number of independent sets in uniform, regular, linear hypergraphs
• A reverse Sidorenko inequality
• Tight bounds on the coefficients of partition functions via stability
• Independent sets, matchings, and occupancy fractions
• Extremal graphs for Widom-Rowlinson colorings in \(k\)-chromatic graphs
• Sidorenko's conjecture, colorings and independent sets
• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• Counting independent sets in cubic graphs of given girth

This page was built for publication: On the Widom-Rowlinson occupancy fraction in regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366940)