Projects per year
Abstract
We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all q ≥ 2. This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of q-colorings of a 3-regular graph, for any q ≥ 2, is maximized by a union of K3,3’s. This proves the d = 3 case of a conjecture of Galvin and Tetali.
Original language | English |
---|---|
Pages (from-to) | 59-75 |
Number of pages | 17 |
Journal | Random Structures and Algorithms |
Volume | 53 |
Issue number | 1 |
Early online date | 4 Feb 2018 |
DOIs | |
Publication status | Published - Aug 2018 |
Keywords
- Potts mode
- partition function
- graph colorings
- graph homomorphims
- Ising model
Fingerprint
Dive into the research topics of 'Extremes of the internal energy of the Potts model on cubic graphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
New approaches to Gibbs measures at the interface of probability and computational complexity
Perkins, W.
Engineering & Physical Science Research Council
1/01/17 → 31/12/18
Project: Research Councils