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
finite set, , . For a function on , let
Recall that Poincaré inequality states that and Log Sobolev inequality states that , with
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.
Example 1 Let where is monotone. Then ,
Pick a total order on . Write
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.
Let be a family of -expanders, i.e. Cheeger constant and maximum degree .
2. If are -regular and have girth tending to infinity,
2.3. Our improvement
Note that the critical probability depends on .
Corollary 5 Choose 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
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.