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

finite set, , . For a function on , let

and

Recall that Poincaré inequality states that and Log Sobolev inequality states that , with

** 1.2. Statement **

Theorem 1 (Falik, Samorodnitsky 2007)Let . Then

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

Example 1Let where is monotone. Then ,

** 1.3. Proof **

Pick a total order on . Write

where

Use concavity of and Jensen’s inequality:

Summing up and applying Jensen again gives an estimate on

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 be a graph, . Study giant connected components of open edges. Existence ? Uniqueness ?

** 2.1. Results in **

On , giant means infinite. Denote by the connected component of the origin. When , define

Then it is known that . Furthermore,

This illustrates Kolmogorov’s law. Recall that sharp threshold results are the finite size analogues of Kolmogorov’s 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 be a family of -expanders, i.e. Cheeger constant and maximum degree .

Theorem 3 (Alon, Benjamini, Stacey 2004)1. There exist constants , , such that2. If are -regular and have girth tending to infinity,

** 2.3. Our improvement **

Let

Theorem 4 (Benjamini, Boucheron, Lugosi, Rossignol)Let be a family of -expanders, i.e. Cheeger constant and maximum degree . For all , has a sharp threshold

Note that the critical probability depends on .

Corollary 5Choose and extract a subsequence such that the probability of converges to some number . Then the conclusion of the second part of Theorem 3 holds.

** 2.4. Proof of Theorem 4 **

Let be the size of the largest connected component in . Let be such that

**Step 1**.

**Step 2**.

Assuming this, take , then, integrating step 2 gives , such that

With step 1, this gives

Use Chebysheff to compare with , and show that , .

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.