Symmetry of Phase Transitions

(sorry, I couldn't find free versions of most of the papers linked to in this post. If you find free versions, please let me know).

One hot research areas of recent times is phase transition phenomena in discrete structures. One of the first examples is that of a random graph. Fix a certain number n of vertices, initially with no edges. Now, add an edge uniformly at random (so you add one of the n(n-1)/2 possible edges , selected at random). Pay attention to a graph property that you like. Let's say the size of the maximally connected subset (that is, the largest subset of the graph such that there is a path between any two vertices). I'll call this the MCS for brevity. Something pretty cool happens when you repeat the process. That is, keep throwing random edges in, keeping track of the size of the MCS. What you will find is that a "phase transition" happens where the MCS suddenly jumps from being very small, to being almost all of the graph. That is, the number of connected components of the graph suddenly decreases. This is very similar to what happens when, say, a liquid transitions to a gas in a physical system, hence the name.

It turns out that these sort of transitions happen in the boolean satisfiability problem also. One example is by tracking the hardness of a problem relative to the clause/variable ratio. A representative publication on this topic is:

Phase Transitions and Backbones of 3-SAT and Maximum 3-SAT. Weixiong Zhang

It turns out that understanding phase transitions may very well be linked to one of my pet topics - symmetries of boolean functions. We look at a slightly different phase transition though.

Say you have a boolean function, f, of n variables. Well, not just any such fundtion. Specifically, f is monotone (so contains no negated atoms) and its automorphism group is transitive. As usual, the automorphism group acts by permuting variables. Now, pick some probability p and assign each variable of f the value 1 independantly with probability p. Let u(p,f) denote the probability that f is satisfied under this assignment. Since u is monotone in p, intervals of values of p pick out a corresponding interval of values of u.

With this in mind, fix some small real e > 0. Define the threshold interval to be the interval [p1,p2] such that u(p1,f) = e and u(p2,f) = 1 - e. In words, this is the interval of probabilities such that f goes from being almost surely unsatisfied to being almost surely satisfied. If this interval is "small", then we have ourselves a phase transition.

Remember that we have some knowledge of how the automorphism group, G, of f acts though. What we do now is to look at the action that G induces on the powerset of variables in f. It turns out that if the orbits of "large" subsets is "large", then the transition interval is small, hence we have ourselves a phase transition. This result crops up in the following paper:

Influences of Variables and Thresholds under Group Symmetries" J. Borgain and G. Kalai.

Now, let us look at what happens in graphs. It turns out that we can be quite general here. A monotone graph property P is one such that if some graph G satisfies P, then every graph on the same set of vertices containing G as a subgraph satisfies P as well. The trick now is to move to something called the Hamming Space and pick out a subset, A, of n points that is "monotone" and is left invariant under some transitive permutation group on that variable set. The threshold interval for A turns out to be very very small indeed. In fact, around O(1/log(n)). From this, one can deduce the same result for montone graph properties. That is, every monotone graph property undergoes a phase transition. That's Cool! This result is contained in:

Every Monotone Graph Property has a Sharp Threshold Ehud Friedgut, Gil Kalai

The natural question then to ask is what the transitive group looks like? In the special case of monotone boolean functions with transitive automorphism group, this amounts asking what the group must be for the function to undergo a phase transition, in the probability sense. Using the usual permutation group trickery, we can answer it for the special case of primitive groups. It turns out that in this case, the group must either be the full alternating or symmetric group on the variable set:

Asymptotic Behaviour of Finite Permutation Groups Acting on Subsets Carmit Benebnisty and Aner Shalev.

Certainly both of these groups satisfy the property that the orbits of "large" subsets are "large", since they both act transitively on the set of k-subsets for any valid k.