On the Threshold
Where the Spins Are
Models of magnetism come in baffling varieties. The basic components are vectors that represent atomic spins. Usually the spins are arranged in a regular lattice, as in a crystalline solid, and the vectors are constrained to point in only a few possible directions. In a model of a ferromagnet, nearby spins have positive couplings, meaning that the energy of the system is lower when the spins line up in parallel. An antiferromagnet has negative couplings, favoring spins that point in different directions. The problem of three-coloring a graph can be seen as a model of an antiferromagnet in which each spin has three possible directions, corresponding to the three colors. It is antiferromagnetic because the favored state is one where the colors or the spins differ.
Most spin-system models focus on the effects of thermal fluctuations and the countervailing imperatives to minimize energy and to maximize entropy. In this respect the graph-coloring model is simpler than most, because the condition of interest is at zero temperature, where entropy can be neglected. On the other hand, the model is more complicated in another way: The spins are embedded in a graph with random interconnections, more like a glass than the geometrically regular lattice of a crystal.
Having translated the coloring problem into the language of spin physics, the aim is to identify the ground state—the spin configuration of minimum energy. If the ground-state energy is zero, then at least one perfect coloring exists. If the energy of the spins cannot be reduced to zero, then the corresponding graph is not three-colorable. The minimum energy indicates how many unavoidable conflicts exist in the colored graph.
Of course recasting the problem in a new vocabulary doesn't make the fundamental difficulty go away. In graph coloring, when you resolve a conflict by changing the color of one vertex, you may create a new conflict elsewhere in the graph. Likewise in the spin system, when you lower the energy of one pair of coupled spins, you may raise it for a different pair. Physicists refer to this effect as "frustration."
Interactions between adjacent spins can be viewed as a kind of message-passing, in which each spin tells its neighbors what they ought to do (or, since the coupling is antiferromagnetic, what they ought not to do). Translating back into the language of graph coloring, a green vertex broadcasts a signal to its neighbors saying "Don't be green." The neighbors send back messages of their own—"Don't be red," "Don't be blue." The trouble is, every edge is carrying messages in both directions, some of which may be contradictory. And feedback loops could prevent the network from ever settling down into a stable state.
A remedy for this kind of frustration is known in condensed-matter physics as the cavity method. It prescribes the following sequence of actions: First, choose a single spin and temporarily remove it from the system (thereby creating a "cavity"). Now, from among the neighbors surrounding the cavity, choose one node to regard as an output and consider the rest to be inputs. Sum up the signals arriving on all the input edges, and pass along the result to the output. The effect is to break open loops and enforce one-way communication. Finally, repeat the entire procedure with another spin, and continue until the system converges on some steady state.
The cavity method was first applied to constraint-satisfaction problems by Marc Mézard of the Université de Paris Sud, Giorgio Parisi of the Università di Roma "La Sapienza" and Riccardo Zecchina of the Abdus Salam International Centre for Theoretical Physics in Trieste. Initially it was a tool for calculating the average properties of statistical ensembles of many spin systems. About a year ago, Mézard and Zecchina realized that it could also be adapted to work with individual problem instances. But a significant change was needed. Instead of simple messages such as "Don't be green," the information transmitted from node to node consists of entire probability distributions, which give a numerical rating to each possible spin state or vertex color.
Mézard and Zecchina named the algorithm survey propagation. They got the "propagation" part from another algorithm that also inspired their work: a technique called belief propagation, which is used in certain error-correcting codes. "Survey" is meant in the sense of opinion poll: The sites surrounding a cavity are surveyed for the advice they would offer to their neighbors.