Percolation crossing

Definition

Let [math]G(V,E)[/math] be a graph with [math]|E| = n[/math] edges, and let [math]A,B \subseteq V[/math] be two disjoint sets of vertices. 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 a 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].

Commonly studied percolation functions are the left-to-right crossing in subcubes of the integer lattice [math]\mathbb{Z}^d[/math], and the left-to-right crossings in rhombuses in the triangular lattice.

Properties

• Noise stability. Plenty of results given in book by Garban and Steif, Noise Sensitivity of Boolean functions and percolation, https://arxiv.org/pdf/1102.5761.pdf .