Notes of Ben Graham’s talk

Influences and the random cluster model

1. Different models

1.1. Percolation

Let {E} denote the set of edges of the square planar grid. Study randomly chosen configurations {\omega:E\rightarrow\{ 0,1 \}}. Denote by

\displaystyle  \begin{array}{rcl}  \omega^e (f)=1 \textrm{ if }e=f, \quad =\omega(f) \textrm{ otherwise}, \end{array}

and

\displaystyle  \begin{array}{rcl}  \omega_e (f)=0 \textrm{ if }e=f, \quad =\omega(f) \textrm{ otherwise}, \end{array}

the configurations obtained from {\omega} by closing or opening one particular edge {e}.

The influence of edge {e} on event {A} is

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(\omega^e \in A \textrm{ and }\omega_e \notin A). \end{array}

For every increasing event {A}, {p\mapsto \mathop{\mathbb P}_p (A)} is increasing.

Kesten, (shorter proof by Bollobas and Riordan) showed that {\mathop{\mathbb P}_p (0 \textrm{ is connected to infinity})} vanishes for {p\leq p_c =\frac{1}{2}}, is positive otherwise.

1.2. Voronoi percolation

Start with a Poisson process on {{\mathbb R}^2}, construct Voronoi cells and study site percolation on the resulting dual graph. Again, almost surely, {p_c =\frac{1}{2}}.

1.3. Site percolation

Back to the square plane lattice. Draw diagonals, get {*}-lattice. Then

\displaystyle  \begin{array}{rcl}  p_c^{\mathrm{site}}+p_{c}^{*,\mathrm{site}}=1. \end{array}

1.4. Ising model

Let {V\subset{\mathbb Z}^2} be a finite subset. Spin configurations are maps {\sigma:V\rightarrow\{\pm 1\}}. The energy of a configuration is

\displaystyle  \begin{array}{rcl}  H(\sigma)=-\frac{1}{2}\sum_{xy\in E}\sigma(x)\sigma(y) -\frac{h}{2}\sum_{x\in V}\sigma(x) \end{array}

Use Gibbs measure

\displaystyle  \begin{array}{rcl}  \phi_{\beta}(\sigma)=\frac{e^{-\beta H(\sigma)}}{Z} \end{array}

where {Z} is a normalizing factor, {\beta} is the inverse temperature.

{\beta} small implies no long range order, correlation {\phi_{\beta}(\sigma(0)\sigma(x))} vanishes when {x} tends to infinity.

Onsager 1944 : {\beta_{c}=\log(1+\sqrt{2})}. {\frac{1}{\beta_c}} is called Curie temperature.

Ising model is related to percolation as follows. Let {\beta<\beta_c}. There exists {h_c} such that if {h>h_c}, {+} spins percolate. There exists {h^*_c} such that if {h>h^*_c}, {+} spins {*}-percolate, and

\displaystyle  \begin{array}{rcl}  h_c +h^*_c =0. \end{array}

1.5. Potts model

Ising model is a special case of Potts model. There, spins are chosen in {[q]}, {q=2,3,\ldots}.

\displaystyle  \begin{array}{rcl}  H(\sigma)&=&-\sum_{xy\in E}1_{\{\sigma(x)=\sigma(y)\}} +const.\\ &=&\sum_{xy\in E}1_{\{\sigma(x)\not=\sigma(y)\}} \end{array}

with probability distribution

\displaystyle  \begin{array}{rcl}  \phi_{\beta,q}=\frac{1}{Z_{\beta,q}}e^{-\beta\sum_{xy\in E}1_{\{\sigma(x)\not=\sigma(y)\}}}. \end{array}

The order parameter is

\displaystyle  \begin{array}{rcl}  \lim_{x\rightarrow \infty}\phi_{\beta}(\sigma(0)=\sigma(x))-\frac{1}{q}. \end{array}

It vanishes for small {\beta}, {\beta<\beta_c} conjectured to be {\log(1+\sqrt{q})} (known if {q=2} and for {q\geq 26}.

1.6. Random cluster model

Let {V\subset{\mathbb Z}^2} be a finite subset. Configurations are maps {\sigma:E\rightarrow\{ 0,1 \}}.

\displaystyle  \begin{array}{rcl}  \mu_{p,q}(\{\omega\})=\frac{q^{k(\omega)}}{Z_{\beta,q}}\prod_{e\in E}p^{\omega(e)}(1-p)^{-\omega(e)}, \end{array}

where {k(\omega)} is the number of clusters (connected components of union of open edges). It looks like bond percolation, without independence.

The probability distribution is

\displaystyle  \begin{array}{rcl}  \nu(\{\sigma,\omega\}=\frac{1}{Z_{\beta,q}}1_{\sigma,\,\omega \,\mathrm{ compatible}}\prod_{e\in E}p^{\omega(e)}(1-p)^{-\omega(e)}. \end{array}

Compatible means…

When {1-p=e^{-\beta}}, this is related to Potts model:

\displaystyle  \begin{array}{rcl}  \sum_{\omega}\nu(\sigma,\omega)=\phi_{\beta,q}(\sigma). \end{array}

There is a {1-1} correspondance. Percolation in the random cluster model exactly corresponds to long range order in the Potts model.

It is conjectured that {SLE(\kappa)} relates to the random cluster model with

\displaystyle  \begin{array}{rcl}  \cos(\frac{4\pi}{\kappa})=-\frac{1}{2}\sqrt{q}, \quad \kappa\in(4,8),\quad q\in(0,4). \end{array}

2. Analysis of the random cluster model

Use two coins, with respective {\frac{1}{3}} and {\frac{2}{3}} bias. Pick a coin uniformly at random and toss it {n} times. The distribution of the sum of results has two peaks at {\frac{n}{3}} and {\frac{2n}{3}}.

Let {A=}Majority. Then influences decrease exponentially with {n}.

2.1. Estimates

Holley’s inequality.

Let {\mu}, {\mu_1}, {\mu_2} be positive measures on {\{ 0,1 \}^n}. If

\displaystyle  \begin{array}{rcl}  \mu_1 (\omega_1 \wedge \omega_2) \mu_1 (\omega_1 \vee \omega_2) \geq \mu_1 (\omega_1) \mu_2 (\omega_2) , \end{array}

then for every event {A},

\displaystyle  \begin{array}{rcl}  \mu_1 (A)\leq\mu_2 (A). \end{array}

FKG inequality.

If

\displaystyle  \begin{array}{rcl}  \mu(\omega_1 \wedge \omega_2) \mu(\omega_1 \vee \omega_2) \geq \mu (\omega_1) \mu(\omega_2) , \end{array}

then for any events {A} and {B},

\displaystyle  \begin{array}{rcl}  \mu(A\cap B)\geq \mu(A)\mu(B). \end{array}

This shows that if {p_1 \leq p_2} and {q\geq 1}, {\mu_{p_1,q}\leq\mu_{p_2,q}}.

For events {F\subset E}, set

\displaystyle  \begin{array}{rcl}  \mu_F^{\xi}=\mu_{p,q}(\cdot|\omega(e)=\xi(e) \textrm{ for all }e\in E\setminus F). \end{array}

Then

\displaystyle  \begin{array}{rcl}  \xi\leq\zeta\quad \Rightarrow\quad\mu_F^{\xi}\leq \mu_F^{\zeta}. \end{array}

2.2. Results

For a monotonic measure {\mu}, define conditional influences

\displaystyle  \begin{array}{rcl}  J_A (e)=\mu(A|\omega(e)=1)-\mu(A|\omega(e)=0). \end{array}

Then

\displaystyle  \begin{array}{rcl}  \frac{d}{dp}\mu_p (A)=\sum_{e}J_A (e). \end{array}

We have both KKL and Talagrand type results.

Theorem 1 (Graham, Grimmet) For a monotonic measure {\mu},

\displaystyle  \begin{array}{rcl}  \max_{e}J_A (e)\geq C\,\mu_p (A)(1-\mu_p (A))\frac{\log N}{N} \end{array}

\displaystyle  \begin{array}{rcl}  \sum_{e}J_A (e)\geq C\,\mu_p (A)(1-\mu_p (A))\log(\frac{1}{2\max_{e}J_A (e)}). \end{array}

In a standard manner, this implies a sharp threshold result

\displaystyle  \begin{array}{rcl}  p_2 -p_1 \leq C\frac{\log(1/\epsilon)}{\log N} \end{array}

if {A} is symmetric, {\mu_{p_1}(A)=\epsilon}, {\mu_{p_2}(A)=1-\epsilon}.

Proof: One compares conditional influences to traditional influences and applies KKL. \Box

2.3. Application

Let {R} be a planar graph and {R'} its dual graph. The dual of the square lattice is again a square lattice. A {(n+1)\times n}-rectangle {R} is dual to a {n\times(n+1)}-rectangle {R'}. In the random cluster model, a configuration on a lattice induces a configuration on the dual lattice. Therefore, if {H} (resp. {V}) denote the events of a horizontal (resp. vertical) crossing in {R} (resp. {R'}),

\displaystyle  \begin{array}{rcl}  \mu_{p,q}(H(R))+\mu_{p_d ,q}(V(R'))=1. \end{array}

This implies that

\displaystyle  \begin{array}{rcl}  \frac{p}{1-p}\frac{p_d}{1-p_d}=q. \end{array}

The probability that a given bond be pivotal tends to {0}, implying a sharp threshold, and

\displaystyle  \begin{array}{rcl}  p_c (q)=\frac{\sqrt{q}}{1+\sqrt{q}}. \end{array}

This is due to Vincent Beffara and Hugo Duminil-Copin.

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