Extremes of the internal energy of the Potts model on cubic graphs

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\ge 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\ge 2$, is maximized by a union of $K_{3,3}$'s. This proves the $d=3$ case of a conjecture of Galvin and Tetali.

References in corpus (3)

• On the average size of independent sets in triangle-free graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Extremal regular graphs: the case of the infinite regular tree

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