Notes of Gil Kalai’s lecture nr 4

1. Sharp threshold phenomena

1.1. Threshold width

Suppose {f:\{0,1\}^n \rightarrow\{0,1\}} is a monotone Boolean function. Then {\mu^p (f)=\mu^p (\{f=1\})} is a non decreasing function of {p}. Russo’s Lemma (appears earlier in Margulis, and even earlier in reliability theory) is

Lemma 1

\displaystyle  \begin{array}{rcl}  \frac{d\mu^p (f)}{dp}=I^p (f):=\sum_{i=1}^n \mu^p(\{f\circ\sigma_k \not=f\}). \end{array}

Definition 2 For {0<\epsilon<1}, let {p_\epsilon (f)} be the value of {p} such that {\mu^p (f)=1-\epsilon}. Call {p_{1/2}(f)} the critical probability for {f}.

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 {f} be a Boolean function describing a monotone graph property for graphs with {v} vertices (here, {n=choose(v,2)}). Then

\displaystyle  \begin{array}{rcl}  |p_{1-\epsilon}(f)-p_{\epsilon}(f)|\leq C\frac{\log\frac{1}{\epsilon}}{\log v}. \end{array}

In other words, the width of the threshold window tends to {0} as {v} tends to infinity.

Proof. The KKL Theorem works equally well for {\mu^p} with the same constant: If {\mu^p (f)=t}, then

\displaystyle  \begin{array}{rcl}  \max_k I_k^p (f)\geq c.t(1-t)\frac{\log n}{n}. \end{array}

If {f} represents a graph property, then all influences {I_k^p (f)} are equal, by symmetry. Thus KKL implies a lower bound {I^p (f)\geq ct(1-t)\log n}. By Russo’s Lemma, the derivative of {\mu^p (f)} is {\geq c\log v} on {[\epsilon,1-\epsilon]}. Some more work needed to have the right dependance on {\epsilon}.

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 {f=1} 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 {G(v,p)} model ? It is {\frac{\log v}{v}}. The threshold window has width {\frac{1}{v}}, which is smaller than given by Theorem 1. We shall see that Theorem 1 is not fully satisfactory in other respects as well.

  1. The critical edge probability for containing a clique of size {\log v} is {\frac{1}{(\log v)^2}}. Where does the square come from ? This has to do with the interplay between symmetry and influence.
  2. What about connectivity ? Here, the critical {p} is very small (a power of {v}).
  3. The threshold behaviour for the {k}-SAT problem (again, {p} is too small).
  4. Margulis and Talagrand extended the Erdös-Renyi result on connectivity in a different direction. Recall that {I(f)=\mathop{\mathbb E}(h)} where {h} is the number of neighbours where {f} changes its value. Replace {h} with its square root. Then {\mathop{\mathbb E}(\sqrt{h})} is bounded below when {\frac{1}{10}\leq\mu^p (f)\leq\frac{9}{10}}.
  5. What is a necessary and sufficient condition for a sequence of Boolean functions to have the sharp threshold property ?
  6. What is the threshold in case {\mu^p (f)} is very small.
  7. Larger alphabets.
  8. Can one sometimes prove {|p_{1-\epsilon}(f)-p_{\epsilon}(f)|\leq \frac{1}{v^{\alpha}}} ?
  9. Other phase transition behaviours for random graph ? When {p} is very small, graph is disconnected, but a transition occurs at {\frac{1}{\log v}}, from a cloud of small components to a giant component.
  10. What about other distributions than {\mu^p} ?

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 {\geq \frac{1}{(\log v)^{2-\epsilon}}}.

1.4. Connectivity

Bollobas: For every {p}, {|p_{1-\epsilon}(f)-p_{\epsilon}(f)|\leq O(p_{1/2})}. So the issue is in replacing {O} with {o}.

Further results by Friedgut, Bourgain, and recently, by Khatami.

1.5. {k}-SAT

Consider Boolean formulas in {m} Boolean variables, in the form of an AND of ORs, where each OR contains {k} 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 {\frac{1}{2}}. This makes {t\sim c.m} clauses. Is there a sharp threshold ?

Where is {p} in this model ? For random graphs, there are two models, {G(n,p)}, which I described, and Erdös-Renyi’s original {G(n,m)} where the number {m} of edges is fixed. In our random formula model, we fix the number {t} of clauses (as in {G(n,m)}), but we could proceed differently: pick each clause at random (as in {G(n,p)}). 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 {m}, there is {c=c(m)} such that if the number {t} of clauses is

  • {t\leq (c-\epsilon)m}, then formula is satisfiable with probability {>1-\delta},
  • {t\geq (c+\epsilon)m}, then formula is unsatisfiable with probability {>1-\delta}.

{c} depends on {m} in an uncontrolled way.

It is a long story, with statistical physics entering. Conjecture. {c(m)} has a limit as {m} 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 {I^p (f)\geq ct(1-t)\log\frac{1}{\epsilon}}.

Consider following Boolean function. There are {n} voters. If the gap between yes and no is {>n^{2/3}}, follow majority. Otherwise, some dictator decides. In this case, influences are not uniformly small. Nevertheless, there is a sharp threshold of width {\frac{1}{\log n}}. Indeed, for {p\not=1/2}, the second case (small majority) arises seldomly. So uniformly small influences is not necessary for a sharp threshold.

1.8. Small values of {\epsilon}

1.9. Small total influence

I.e. {I(f)\sim\frac{1}{v^{\alpha}}}. 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 {t^{|\{\mathrm{connected\, components}\}|}}.

There is an analogue of KKL which applies to Pott’s model.

2. The influence-entropy conjecture

I develop Problem 1.

Consider Boolean functions {f}. Then one can think of squares of Fourier coefficients as a probability distribution over subsets of {[n]}.

Conjecture (Friedgut, Kalai). There is an absolute constant {c} such that the entropy

\displaystyle  \begin{array}{rcl}  I(f)\geq c\sum_{S}\hat{f}_S^2 \log\frac{1}{\hat{f}_S^2}. \end{array}

Consequence. If {f} represents a monotone graph property on {v} vertices, then {I^p (f)\geq c(\log v)^2}, and thus threshold width is {\leq \frac{1}{(\log v)^2}}.

Note that a linear map of {({\mathbb Z}/2{\mathbb Z})^n} 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 {[n]} correspond to subgraphs. By assumption, {\hat{f}_S} only depends on the isomorphism type of the subgraph associated to {S}. What is the smallest number {m} of edges of a graph such that the number of graphs isomorphic to it is {\leq 2^m} ? They contribute {m} 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 {\log v} vertices and so at least {(\log v)^2} edges. This implies {I(f)\geq (\log v)^2}, and explain the threshold width.

3. CNS for sharp threshold

Definition 6 Say a sequence {(f_n)} of Boolean functions has sharp threshold if

\displaystyle  \begin{array}{rcl}  |p_{\epsilon}(f_n)-p_{1-\epsilon}(f_n)|=o(p_{1/2}(f)). \end{array}

Say a sequence {(f_n)} has coarse threshold if

\displaystyle  \begin{array}{rcl}  |p_{\epsilon}(f_n)-p_{1-\epsilon}(f_n)|\sim p_{1/2}(f). \end{array}

Example 2 {G} contains a triangle. Critical probability is {1/n}.

{G} contains a fixed graph {H}. Critical probability is {\frac{1}{n^{\alpha(H)}}}, where {\alpha(H)} is rational and easy to compute.

From a result of Friedgut, it follows that if {p_{1/2} (f_n) \not=\frac{1}{n^{\alpha}}} with {\alpha} a rational number, then there is a sharp threshold.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course, Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s