There is a simple connection between ground states of antiferromagnetic Potts models and colorings of the plane: if the unit distance graph of the plane ($G=(\mathbb R^2,\{\{x,y\},d_2(x,y)=1\})$) is admissibly colored with $q$ colors, then this is a ground state of the $q$-state Potts model, and conversely, a ground state without frustration (therefore with trivially computed energy and ground state entropy) yields a coloring of $G$.

But the recent advances in our understanding of the ferromagnetic Potts models let us hope that a related statistical physics connection could yield insight into the chromatic number of the plane. Duminil-Copin et al. have proved that the phase transition for the Potts model is continuous up to and including $q=4$ states. And it is discontinuous/1st order for $q\ge 26$ and conjectured to be for 5 and more states. These results are for the square lattice but they have obtained related results on isoradial subgraphs of the plane, many such graphs are subgraphs of $G$. It seems on page 5 they conjecture that for all planar graphs the nature of the transition is the same given a number of states $q$. It seems to me that this should be interpreted as a hint that the chromatic number of the plane is 5. I think that Erdos and other experts never really knew what to believe about that number, which is 4, 5, 6, or 7. The usual example for a non-3-colorable subgraph is Moser's spindle. While a hexagonal tiling with different colors on adjacent tiles give an admissible 7-coloring.

The rationale for phase transitions at $q>4$ yielding admissible colorings could be, I am guessing, that if $G$ is $q$-colorable it is possible with $q$ states to have an ordered phase, with an infinite cluster (thus not admissible), at $T=T_t$ (say adiabatically continued raising temperature from $T<T_t$) coexist with a lower energy disordered phase, i.e. with small finite clusters (i.e. avoiding distance 1, of diameter<1), at the same temperature. This is a characteristic of discontinuous transitions (like water/gas below critical point) that there are 2 phases with different energies at the same temperature at the transition $T=T_t$.

So what do probabilists and statistical physicists think of this possible link? When you prove discontinuous phase transition what is the measure of the different phases at transition temperature? Can you have systems with big measure for only one side (ordered or disordered) of the transition?

Thanks a lot for any comments.

EDIT: I fixed a couple of my statements and added references. A quick description of the Potts model is that it is a generalization of the Ising model where the "spins" can take more than 2 values on the unit circle and the repulsion energy is proportional to the scalar product of those times a constant coefficient $J$, positive=ferromagnetic (adjacent spins tend to oppose), negative=antiferromagnetic. The energy can be simplified to just a delta function between spins instead of scalar product. The partition function at temp $1/\beta$ is $Z(\beta)=\sum_\sigma e^{-\beta\sum H(\sigma_{ij})}$ with $H(\sigma_{ij})$ the energy contribution from the $ij$ sites interaction in state $\sigma$.

2ND EDIT: The rationale for considering Potts models is trying to find a "local" interaction which would create proper colorings of $G$ by favoring adjacent spins to be aligned but far enough spins to be unaligned with high enough probability. The Potts model at high temperature favors some random flipping at mid distance while keeping adjacent spins clustering on the same color. So the clusters should not be too large and yield proper colorings "usually". Another justification I would bring is that proper colorings should have a complicated structure which would look random and that the only way of yielding that seems to be the "probabilistic method" and apart from local laws for constraining the desired properties on coloring I do not see what would. And local interactions should have all been considered by physicists, and finally because of the universality of behaviors for many classes of interactions looking at Potts models with various parameters should be hopefully enough to find the right universality class to build at least on some "visible" part of phase space (i.e. with positive propability, or for typical states in simulations with Boltzmann/Gibbs measure) proper colorings, at least on some part of the plane and then we can tile the whole plane with that part. Well I just try to write what comes up to me. Sorry for likers of clear thoughts.

Question of calculating the chromatic number of the plane


Duminil-Copin's review at CDM conference

Some of Sokal's papers for a combinatorialist view on antiferromagnetic Potts models: https://arxiv.org/abs/cond-mat/9910503 https://arxiv.org/abs/cond-mat/0004231 https://arxiv.org/abs/math/0503607

A physicist's survey of Potts models http://www.yaroslavvb.com/papers/wu-potts.pdf

Actually I found out the Duminil-Copin et al. have proved their conjecture that the phase transition is discontinuous (as long "physically" proved by physicists). http://www.ihes.fr/~duminil/publi/2016discontinuousPotts.pdf

  • 3
    $\begingroup$ You should say more about the Potts model, your first paragraph is unclear to me and probably many others. The article you link to is interested in Potts model on $\mathbb{Z}^2$, very unlikely to have a connexion with the Hadwiger-Nelson problem (which has no reason to be insensitive to small perturbations of the distance). $\endgroup$ – Benoît Kloeckner Jun 23 '17 at 6:40
  • $\begingroup$ Actually as I added in my edit all planar Potts models should have the same type of phase transition. It does sound paradoxical. $G$ also contains lots of nonplanar subgraphs. But I guess rescaling graphs by a conformal transformation may explain the conjectured uniformity of behavior. Also for q=4 the phase transition is critical so typical configurations at $T_c$ are unchanged under conformal mappings, but the colorings are not admissible. It is not clear to me how all this fits together but I feel that admissible colorings of $G$ should look like appropriate Potts models states at $T_t$. $\endgroup$ – plm Jun 25 '17 at 2:48
  • $\begingroup$ I should have said $q\le 3$ and conjecturally for $q=4$ no coloring is admissible (according to my protoheuristic). $\endgroup$ – plm Jun 25 '17 at 3:47

I'm not an expert, but I believe your question is predicated on something which is not true. In particular, the antiferromagnetic (AF) Potts model and the ferromagnetic Potts model exhibit very different phases and phase transitions, so features of the ferromagnetic Potts phase transitions do not necessarily have counterparts in the AF Potts model and hence are unlikely to have consequences for the graph coloring problem.

As you mention, it is believed that the 2D ferromagnetic Potts model transition between order and disorder occurs at finite temperatures and is continuous for $q\leq 4$ and discontinuous for $q>4$. Furthermore, this is expected to hold for all infinite "2D" graphs (the "universality" property).

However, the phase transitions in the 2D AF Potts model are believed to be rather different. It is expected that for some $q_c$ which depends on the lattice, when $q>q_c$ there are no phase transitions at all -- the system is disordered even at zero temperature. When $q<q_c$, the AF Potts model then usually exhibits a phase transition at finite temperature, but not always. If it does then it might be first-order or continuous, but this behavior and even $q_c$ depends on the underlying lattice and is non-universal.

These differences illustrate my claim above -- the ferromagnetic and AF Potts phase transitions are quite different beasts.

See for example the discussion in these slides by Jan M. Swart, or the introduction to the paper "Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem" by Salas and Sokal.

As an aside, you may be interested in the phenomenon of "Beraha numbers" which have appeared in a question on this site before.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.