The Widom–Rowlinson model, the hard-core model and the extremality of the complete graph
| Autor: | Emma Cohen, Péter Csikvári, Will Perkins, Prasad Tetali |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Large class
Conjecture Simple graph 010102 general mathematics Complete graph 0102 computer and information sciences 01 natural sciences Hard core Graph Vertex (geometry) Combinatorics 010201 computation theory & mathematics Bijection Discrete Mathematics and Combinatorics 0101 mathematics Mathematics |
| Zdroj: | European Journal of Combinatorics. 62:70-76 |
| ISSN: | 0195-6698 |
| DOI: | 10.1016/j.ejc.2016.11.003 |
| Popis: | 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 ( K d + 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 ( K d + 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect