On the Widom-Rowlinson occupancy fraction in regular graphs

DOI10.1017/S0963548316000249zbMATH Open1371.05182arXiv1512.06398OpenAlexW2963760054MaRDI QIDQ5366940FDOQ5366940

Authors: Emma Cohen, Will Perkins, Prasad Tetali 

Publication date: 10 October 2017

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• 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
• Tight bounds on the coefficients of partition functions via stability
• A reverse Sidorenko inequality
• 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
• Extremal regular graphs: independent sets and graph homomorphisms

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)