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.

Advertisements

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 http://www.math.ens.fr/metric2011/
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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s