Percolation crossing

Motivation

The theory of percolation studies the connectivity and large-scale clusters of graphs from which edges / vertices are randomly removed. The classical mathematical theory of percolation deals with infinite graphs, and asks whether or not there is an infinite component after the edges / vertices have been removed. A crucial element in this analysis is figuring whether or not there are paths connecting certain different finite sets. This lets us define functions on finite graphs.

General definition

Let [math]G(V,E)[/math] a graph, and let [math]A,B \subseteq V[/math] be two disjoint sets of vertices.

Edge percolation

Let [math]n = |E|[/math]. Every vector [math]x \in \{-1,1\}^n[/math] can be seen as a labeling on the edges of [math]G[/math]: An edge [math]e_i[/math] is called "open" if [math]x_i = 1[/math] and "closed" if [math]x_i = -1[/math]. A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called an edge-percolation crossing function if under the labeling of open and closed edges given by [math]x[/math], there exists an open path from [math]A[/math] to [math]B[/math].

Site percolation

Let [math]n = |V|[/math]. Every vector [math]x \in \{-1,1\}^n[/math] can be seen as a labeling on the vertices of [math]G[/math]: A vertex [math]v_i[/math] is called "open" if [math]x_i = 1[/math] and "closed" if [math]x_i = -1[/math]. A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a site-percolation crossing function if under the labeling of open and closed vertices given by [math]x[/math], there exists an open path from [math]A[/math] to [math]B[/math] (i.e, the path has neighbors both in [math]A[/math] and in [math]B[/math]).

Common usage

While percolation crossing functions can be defined for any graph and any sets [math]A[/math] and [math]B[/math], there are two specific functions which have been heavily studied:

• Left-to-right edge-percolation crossings in [math]N \times N[/math] squares of the two-dimensional integer lattice [math]\mathbb{Z}^2[/math].
• Left-to-right site-percolation crossings in the [math]N \times N[/math] rhombus of the two-dimensional triangular lattice [math]\mathbb{T}[/math].

The properties below therefore relate to these two functions.

Properties

• Both for edge-percolation in [math]\mathbb{Z}^2[/math] and site-percolation in [math]\mathbb{T}[/math], [math]f[/math] is balanced.
• Noise stability. TODO! Plenty of results given in book by Garban and Steif, Noise Sensitivity of Boolean functions and percolation, https://arxiv.org/pdf/1102.5761.pdf .