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. The Potts model is a probabilistic model of interacting spins on a graph. Here, we use the term color instead of spin to highlight a connection to extremal combinatorics which we cover in Section 2. Let G = (V, E) be a graph and σ ∈ [q] V (G) a coloring (not necessarily proper) of the vertices of G with q possible colors. Let m(σ) denote the number of monochromatic edges of G under σ. Then the q-color Potts model partition function is: .
In REF , the method is applied to models with soft constraints, namely the Ising and Potts models on regular graphs, which in the 'zerotemperature limit' yield extremal bounds on the number of q-colorings of cubic graphs.
Extremes of the internal energy of the Potts model on cubic graphs
arXiv: Combinatorics
Mathematics Computer Science