## 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

Talagrand

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.