# 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 $G(V,E)$ a graph, and let $A,B \subseteq V$ be two disjoint sets of vertices.

### Edge percolation

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

### Site percolation

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

## Common usage

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

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

The properties below therefore relate to these two functions.

## Properties

• Both for edge-percolation in $\mathbb{Z}^2$ and site-percolation in $\mathbb{T}$, $f$ 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 .