1. Sharp threshold phenomena
1.1. Threshold width
Suppose is a monotone Boolean function. Then is a non decreasing function of . Russo’s Lemma (appears earlier in Margulis, and even earlier in reliability theory) is
Definition 2 For , let be the value of such that . Call the critical probability for .
We are interested in monotone graph properties. By a graph property, we mean a property that is invariant under permutation of the vertices.
Example 1 The fact a graph is connected is monotone. The fact a graph contains a Hamiltonian cycle is monotone. The fact a graph contains a clique of a given size is monotone.
Theorem 3 Let be a Boolean function describing a monotone graph property for graphs with vertices (here, ). Then
In other words, the width of the threshold window tends to as tends to infinity.
Proof. The KKL Theorem works equally well for with the same constant: If , then
If represents a graph property, then all influences are equal, by symmetry. Thus KKL implies a lower bound . By Russo’s Lemma, the derivative of is on . Some more work needed to have the right dependance on .
All we used is the existence of a symmetry group permuting coordinates transitively. In this generality, the theorem is sharp. Take the tribes example. An other example: put bits at vertices of a cycle. Let iff the longest run of 1’s is longer than the longest run of 0’s.
1.2. Further questions
What is the critical edge probability of connectivity in the Erd\” os-Renyi model ? It is . The threshold window has width , which is smaller than given by Theorem 1. We shall see that Theorem 1 is not fully satisfactory in other respects as well.
- The critical edge probability for containing a clique of size is . Where does the square come from ? This has to do with the interplay between symmetry and influence.
- What about connectivity ? Here, the critical is very small (a power of ).
- The threshold behaviour for the -SAT problem (again, is too small).
- Margulis and Talagrand extended the Erdös-Renyi result on connectivity in a different direction. Recall that where is the number of neighbours where changes its value. Replace with its square root. Then is bounded below when .
- What is a necessary and sufficient condition for a sequence of Boolean functions to have the sharp threshold property ?
- What is the threshold in case is very small.
- Larger alphabets.
- Can one sometimes prove ?
- Other phase transition behaviours for random graph ? When is very small, graph is disconnected, but a transition occurs at , from a cloud of small components to a giant component.
- What about other distributions than ?
Next, I rapidly quote a few results on these questions. Later on, I will come back to some of them in some detail.
1.3. Relation between symmetry group and total influence
Theorem 4 (Bourgain, Kalai) For every primitive symmetry group, threshold width is .
Bollobas: For every , . So the issue is in replacing with .
Further results by Friedgut, Bourgain, and recently, by Khatami.
Consider Boolean formulas in Boolean variables, in the form of an AND of ORs, where each OR contains of the variables, eventually negated. Pick such formulas at random. Choose the number of clauses so that the probability that a formula be satisfiable is . This makes clauses. Is there a sharp threshold ?
Where is in this model ? For random graphs, there are two models, , which I described, and Erdös-Renyi’s original where the number of edges is fixed. In our random formula model, we fix the number of clauses (as in ), but we could proceed differently: pick each clause at random (as in ). This is this second model which is convenient for proving theorems, but the two are equivalent to a great extent.
Theorem 5 (Friedgut) 3-SAT has a sharp threshold. For every , there is such that if the number of clauses is
- , then formula is satisfiable with probability ,
- , then formula is unsatisfiable with probability .
depends on in an uncontrolled way.
It is a long story, with statistical physics entering. Conjecture. has a limit as tends to infinity.
1.6. Boundary and influences
1.7. Different CNS for sharp thresholds
The proof of KKL gives the following statement: if all influences are small, then total influence .
Consider following Boolean function. There are voters. If the gap between yes and no is , follow majority. Otherwise, some dictator decides. In this case, influences are not uniformly small. Nevertheless, there is a sharp threshold of width . Indeed, for , the second case (small majority) arises seldomly. So uniformly small influences is not necessary for a sharp threshold.
1.8. Small values of
1.9. Small total influence
I.e. . We have no tools.
1.10. Other distributions
Product measures are often unnatural. For instance, in Potts’ model, probability of a configuration of open/closed edges is multiplied with an extra weight .
There is an analogue of KKL which applies to Pott’s model.
2. The influence-entropy conjecture
I develop Problem 1.
Consider Boolean functions . Then one can think of squares of Fourier coefficients as a probability distribution over subsets of .
Conjecture (Friedgut, Kalai). There is an absolute constant such that the entropy
Consequence. If represents a monotone graph property on vertices, then , and thus threshold width is .
Note that a linear map of does not change entropy, but can change total influence drasticly, so the inequality is surprising.
Every permutation of vertices acts as a permutation of coordinates (i.e. edges). Subsets of correspond to subgraphs. By assumption, only depends on the isomorphism type of the subgraph associated to . What is the smallest number of edges of a graph such that the number of graphs isomorphic to it is ? They contribute to influence, but much more to entropy. So the conjecture helps answering this question. Consider cliques: conjecture implies that the Fourier coefficients of graph properties are concentrated on subsets (cliques) with at least vertices and so at least edges. This implies , and explain the threshold width.
3. CNS for sharp threshold
Definition 6 Say a sequence of Boolean functions has sharp threshold if
Say a sequence has coarse threshold if
Example 2 contains a triangle. Critical probability is .
contains a fixed graph . Critical probability is , where is rational and easy to compute.
From a result of Friedgut, it follows that if with a rational number, then there is a sharp threshold.