Notes of Raphael Rossignol’s talk

Sharp threshold for percolation on expanders

We discuss a functional inequality related to Talagrand’s inequality. And then give an application to percolation.

1. Functional inequality

1.1. Notation

{E} finite set, {\Omega=\{ 0,1 \}Ê}, {\mathop{\mathbb P}_p =\mathcal{B}(p)^{\otimes E}}. For a function {f} on {\Omega}, let

\displaystyle  \begin{array}{rcl}  \nabla_{e}f(\omega)=f(\omega^e)-f(\omega_e), \end{array}

\displaystyle  \begin{array}{rcl}  \Delta_e f(\omega)=f(\omega)-\int f(\omega)d\omega_e = \nabla_{e}f(\omega)((1-p)1_{\omega_e =1}-p1_{\omega_e =0}), \end{array}


\displaystyle  \begin{array}{rcl}  L=-\sum_{e}\Delta_e ,\quad E(f)=\mathop{\mathbb E}_p (-f Lf). \end{array}

Recall that Poincaré inequality states that {Var_p (f)=E(f)} and Log Sobolev inequality states that {Ent_p (f^2)\leq c_{LS}(p) E(f)}, with

\displaystyle  \begin{array}{rcl}  c_{LS}(p)=\frac{\log p -\log(1-p)}{p-(1-p)}. \end{array}

1.2. Statement

Theorem 1 (Falik, Samorodnitsky 2007) Let {E_1 (f):=\sum_{e}\|\Delta_e f \|_1^2}. Then

\displaystyle  \begin{array}{rcl}  Var_p (f)\log\frac{Var_p (f)}{E_1 (f)}\leq c_{LS}(p)E(f). \end{array}

In many cases, it is equivalent to Talagrand’s inequality. It implies it, and gives the best known estimate on the constant in the KKL theorem.

Corollary 2

\displaystyle  \begin{array}{rcl}  Var_p (f)\leq 2c_{LS}(p)\frac{E(f)}{\log\frac{E(f)}{E_1 (f)}}. \end{array}

Example 1 Let {f=1_A} where {A} is monotone. Then {E(f)=p(1-p)Inf(f)},

\displaystyle  \begin{array}{rcl}  E_1 (f)=(2p(1-p))^2 \sum_{e\in E}Inf_e (f)^2 . \end{array}

1.3. Proof

Pick a total order on {E}. Write

\displaystyle  \begin{array}{rcl}  f-\mathop{\mathbb E}_p (f)=\sum_{e\in E}f_e \end{array}


\displaystyle  \begin{array}{rcl}  f_e &=&\mathop{\mathbb E}_p (f|(\omega_{e'})_{e'\leq e})-\mathop{\mathbb E}_p (f|(\omega_{e'})_{e'< e})\\ &=&\mathop{\mathbb E}_p (\Delta_e f|(\omega_{e'})_{e'\leq e}). \end{array}

Use concavity of {\log} and Jensen’s inequality:

\displaystyle  \begin{array}{rcl}  Ent_p (f_e^2)&=&\mathop{\mathbb E}_p (f_e^2 \log\frac{f_e^2}{\mathop{\mathbb E}_p (f_e^2)})\\ &=&\frac{2\mathop{\mathbb E}_p (-f_e^2 \log\frac{\|f_e^2\|}{|f_e|})}{\mathop{\mathbb E}_p (f_e^2)}\mathop{\mathbb E}_p (f_e^2)\\ &\geq&-2\mathop{\mathbb E}_p (f_e^2)\log(\mathop{\mathbb E}_p(\frac{f_e^2}{\mathop{\mathbb E}_p (f_e^2)}\frac{\|f_e^2\|}{|f_e|}))\\ &=&\mathop{\mathbb E}_p (f_e^2)\log\frac{\mathop{\mathbb E}_p (f_e^2)}{\mathop{\mathbb E}_p (|f_e|)^2}\\ &\geq&\mathop{\mathbb E}_p (f_e^2)\log\frac{\mathop{\mathbb E}_p (f_e^2)}{\mathop{\mathbb E}(|\Delta_e f|)^2}. \end{array}

Summing up and applying Jensen again gives an estimate on

\displaystyle  \begin{array}{rcl}  \sum_{e\in E}Ent_p (f_e^2) \end{array}

Using Log Sobolev Inequality gives the Theorem.

2. Application to bond percolation

Unlike most applications, which provide comparison with a symmetric situation, there will be no symmetry here.

Let {G=(V,E)} be a graph, {\Omega=\{ 0,1 \}^E}. Study giant connected components of open edges. Existence ? Uniqueness ?

2.1. Results in {{\mathbb Z}^d}

On {{\mathbb Z}^d}, giant means infinite. Denote by {C_0} the connected component of the origin. When {d\geq 2}, define

\displaystyle  \begin{array}{rcl}  p^* =\inf\{p\,;\,\mathop{\mathbb P}_p (|C_0|=\infty)>0\}. \end{array}

Then it is known that {0<p^* <1}. Furthermore,

\displaystyle  \begin{array}{rcl}  p>p^* \quad&\Rightarrow&\quad \mathop{\mathbb P}_p (\exists \textrm{ infinite component})=1,\\ p<p^* \quad&\Rightarrow&\quad \mathop{\mathbb P}_p (\exists \textrm{ infinite component})=0. \end{array}

This illustrates Kolmogorov’s {0-1} law. Recall that sharp threshold results are the finite size analogues of Kolmogorov’s {0-1} law.

Following Benjamini and Schramm 1999, we are interested in other graphs, including finite graphs. Then giant means of linear size. Alon, Benjamini and Stacey 2004 prove uniqueness of giant component for expanders, and existence for regular high girth expanders. I will explain how one can remove the regularity and high girth assumptions.

2.2. ABS

Let {(G_n)} be a family of {(b,d)}-expanders, i.e. Cheeger constant {\geq b} and maximum degree {\leq d}.

Theorem 3 (Alon, Benjamini, Stacey 2004) 1. There exist constants {\omega(b,d)<1}, {K(b,d)}, {g(b,d)>0} such that

\displaystyle  \begin{array}{rcl}  \sup_p \mathop{\mathbb P}_p(\exists \textrm{ at least }2\textrm{ connected components of size }\geq n^{\omega})\leq K\,n^{-g}. \end{array}

2. If {(G_n)} are {d}-regular and have girth {g_n} tending to infinity,

\displaystyle  \begin{array}{rcl}  p>\frac{1}{d-1}&\Rightarrow&\exists c>0 \textrm{ such that } \mathop{\mathbb P}_p (\exists \textrm{ a connected component of size }\geq c\,n)=1,\\ p<\frac{1}{d-1}&\Rightarrow&\forall c>0,\quad \mathop{\mathbb P}_p (\exists \textrm{ a connected component of size }\geq c\,n)=0. \end{array}

2.3. Our improvement


\displaystyle  \begin{array}{rcl}  A_n (c)=\{\exists \textrm{ a connected component of size }\geq c\,n\}. \end{array}

Theorem 4 (Benjamini, Boucheron, Lugosi, Rossignol) Let {(G_n)} be a family of {(b,d)}-expanders, i.e. Cheeger constant {\geq b} and maximum degree {\leq d}. For all {c\in(0,1)}, {A_n (c)} has a sharp threshold

\displaystyle  \begin{array}{rcl}  p_2 -p_1 \leq O(\frac{1}{(\log n)^{1/3}}). \end{array}

Note that the critical probability depends on {c}.

Corollary 5 Choose {c_n} and extract a subsequence such that the probability of {A_n (c_n)} converges to some number {p^*}. Then the conclusion of the second part of Theorem 3 holds.

2.4. Proof of Theorem 4

Let {L_n} be the size of the largest connected component in {G_n}. Let {p_{\alpha}} be such that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}_{p_{\alpha}}(L_n \geq cn)=\alpha. \end{array}

Step 1.

\displaystyle  \begin{array}{rcl}  \frac{d}{dp}\mathop{\mathbb E}_p (L_n)\geq c(\alpha)n \quad \textrm{ if }p\in[p_{\alpha},p_{1-\alpha}]. \end{array}

Step 2.

\displaystyle  \begin{array}{rcl}  Var_p (L_n)\leq C(b,d)\frac{n}{\log n}\frac{d\mathop{\mathbb E}_p (L_n)}{dp}. \end{array}

Assuming this, take {\epsilon_n=\frac{K}{(\log n)^{1/3}}}, then, integrating step 2 gives {q_1 \in (p_{1/2},p_{1/2 +\epsilon_n /3})}, {q_2 \in (p_{1/2 +2\epsilon_n /3},p_{1/2 +\epsilon_n})} such that

\displaystyle  \begin{array}{rcl}  Var_{q_i} (L_n)\leq C\frac{n^2}{K(\log n)^{2/3}}. \end{array}

With step 1, this gives

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_{q_2}(L_n)\geq \mathop{\mathbb E}_{q_1}(L_n)+C\frac{nKc(\alpha)}{3(\log n)^{1/3}}. \end{array}

Use Chebysheff to compare {\mathop{\mathbb E}_{q_i}} with {L_n}, and show that {p_{1-\alpha}\leq q_2}, {p_{\alpha}\geq q_1}.

Step 1 is Russo’s formula plus expansion. Indeed, when one adds an edge, the giant component increases by a definite amount, this gives a lower bound on influences.

Theorems 1 and 3 are used in step 2.


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