Extremes of the internal energy of the Potts model on cubic graphs
arXiv:1610.08496 · doi:10.1002/rsa.20767
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 . 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 -colorings of a -regular graph, for any , is maximized by a union of 's. This proves the case of a conjecture of Galvin and Tetali.
References in corpus (10)
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
- Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
- The Bethe Partition Function of Log-supermodular Graphical Models
- On the average size of independent sets in triangle-free graphs
- Extremal regular graphs: independent sets and graph homomorphisms
- The Bipartite Swapping Trick on Graph Homomorphisms
- Independent Sets, Matchings, and Occupancy Fractions
- Maximizing the number of q-colorings
- Extremal regular graphs: the case of the infinite regular tree
- Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
Cited by in corpus (5)
- Extremal regular graphs: independent sets and graph homomorphisms
- The number of independent sets in an irregular graph
- Extremal regular graphs: the case of the infinite regular tree
- Counting proper colourings in 4-regular graphs via the Potts model
- Tight bounds on the coefficients of partition functions via stability