Difference between revisions of "Percolation crossing"
m (→Properties) |
m |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | == | + | == 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 == | == Properties == | ||
| + | * Both for edge-percolation in <math>\mathbb{Z}^2</math> and site-percolation in <math>\mathbb{T}</math>, <math>f</math> is [[Balanced function | 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 . | * 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 . | ||
| Line 10: | Line 25: | ||
<references/> | <references/> | ||
| − | [[Category:Monotone function]] | + | [[Category:Monotone function]] [[Category:Balanced function]] [[Category: Noise sensitive function]] |
Latest revision as of 14:35, 7 April 2021
Contents
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 .
