Counting proper colourings in 4-regular graphs via the Potts model (Q1991414)

Summary: We give tight upper and lower bounds on the internal energy per particle in the antiferromagnetic \(q\)-state Potts model on 4-regular graphs, for \(q\geq 5\). This proves the first case of a conjecture of \textit{E. Davies} et al. [Random Struct. Algorithms 53, No. 1, 59--75 (2018; Zbl 1401.05108)], and implies tight bounds on the antiferromagnetic Potts partition function. The zero-temperature limit gives upper and lower bounds on the number of proper \(q\)-colourings of 4-regular graphs, which almost proves the case \(d=4\) of a conjecture of Galvin and Tetali. For any \(q \geq 5\) we prove that the number of proper \(q\)-colourings of a 4-regular graph is maximised by a union of \(K_{4,4}\)'s.