Difference between revisions of "Extended butterfly percolation"
(Created page with "== Definition == These are a type of percolation crossing function, for which the revealment can be analyzed. The '''extended butterfly graph''' is defined as follows...") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | These are a type of [[percolation crossing]] function, for which the [[revealment]] can be analyzed. | + | These are a type of [[percolation crossing]] function, for which the [[revealment]] can be very precisely analyzed. |
The '''extended butterfly graph''' is defined as follows. Let <math>H,W</math> be positive integers, where <math>H</math> is a power of 2. The vertices of the extended butterfly are pairs <math>(h,t)</math>, with <math>0 \leq h < H</math> and <math>0 \leq t < W</math>. The edges are directed, and each vertex has two outgoing edges: <math>(h,t) \mapsto (2h, t+1)</math> and <math>(h,t) \mapsto (2h+1, t+1)</math>, where arithmetic is done modulo <math>H</math> and <math>W</math>. Thus the graph has <math>2WH</math> edges. | The '''extended butterfly graph''' is defined as follows. Let <math>H,W</math> be positive integers, where <math>H</math> is a power of 2. The vertices of the extended butterfly are pairs <math>(h,t)</math>, with <math>0 \leq h < H</math> and <math>0 \leq t < W</math>. The edges are directed, and each vertex has two outgoing edges: <math>(h,t) \mapsto (2h, t+1)</math> and <math>(h,t) \mapsto (2h+1, t+1)</math>, where arithmetic is done modulo <math>H</math> and <math>W</math>. Thus the graph has <math>2WH</math> edges. | ||
| Line 9: | Line 9: | ||
We can now define two functions, based on the two percolation models above: | We can now define two functions, based on the two percolation models above: | ||
| − | * Edge selection: The resulting graph necessarily has a cycle, so there must be a vertex <math>(h,0)</math> with minimal <math>h</math> that is in a cycle. Let <math>f_1: \{-1,1\}^{HW} \to {-1,1}</math> be the parity of <math>h</math>: | + | * Edge selection: The resulting graph necessarily has a cycle, so there must be a vertex <math>(h,0)</math> with minimal <math>h</math> that is in a cycle. Let <math>f_1: \{-1,1\}^{HW} \to \{-1,1\}</math> be the parity of <math>h</math>: |
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
| Line 16: | Line 16: | ||
|} | |} | ||
| − | * Bond percolation: Let <math>f_2: \{-1,1\}^{2HW}</math> return 1 if there is a cycle of length <math>W</math>: | + | * Bond percolation: Let <math>f_2: \{-1,1\}^{2HW} \to \{-1,1\}</math> return 1 if there is a cycle of length <math>W</math>: |
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
Latest revision as of 07:18, 26 March 2021
Definition
These are a type of percolation crossing function, for which the revealment can be very precisely analyzed.
The extended butterfly graph is defined as follows. Let [math]H,W[/math] be positive integers, where [math]H[/math] is a power of 2. The vertices of the extended butterfly are pairs [math](h,t)[/math], with [math]0 \leq h \lt H[/math] and [math]0 \leq t \lt W[/math]. The edges are directed, and each vertex has two outgoing edges: [math](h,t) \mapsto (2h, t+1)[/math] and [math](h,t) \mapsto (2h+1, t+1)[/math], where arithmetic is done modulo [math]H[/math] and [math]W[/math]. Thus the graph has [math]2WH[/math] edges.
Here are two possible percolation models on the graph:
- Edge-selection: To each vertex [math](h,t)[/math] we associate a bit [math]x_i[/math]. If [math]x_i = 1[/math], then keep only the edge [math](h,t) \mapsto (2h, t+1)[/math]; else, keep only the edge [math](h,t) \mapsto (2h+1, t+1)[/math].
- Bond percolation: To each edge we associate a bit [math]x_i[/math]. If [math]x_i = 1[/math], keep the edge; else, remove it.
We can now define two functions, based on the two percolation models above:
- Edge selection: The resulting graph necessarily has a cycle, so there must be a vertex [math](h,0)[/math] with minimal [math]h[/math] that is in a cycle. Let [math]f_1: \{-1,1\}^{HW} \to \{-1,1\}[/math] be the parity of [math]h[/math]:
[math] f(x) = \begin{cases} 1, & \mathrm{if} ~ h \mod 2 = 1\\ -1 & \text{otherwise} \end{cases}[/math]
- Bond percolation: Let [math]f_2: \{-1,1\}^{2HW} \to \{-1,1\}[/math] return 1 if there is a cycle of length [math]W[/math]:
[math] f(x) = \begin{cases} 1, & \exists \text{ cycle of length } W\\ -1 & \text{otherwise} \end{cases}[/math]
Properties
- The function [math]f_1[/math] is balanced. With proper choice of [math]H[/math] and [math]W[/math], the function [math]f_2[/math] can be made balanced as well.
- The function [math]f_2[/math] is monotone.
- There exists a revealment algorithm that calculates [math]f_1[/math] with query probability [math]\delta = \Theta(n^{-1/2}\sqrt{\log n})[/math]. Similarly, there exists a revealment algorithm that calculates [math]f_2[/math] with query probability [math]\delta = \Theta(n^{-1/3}\log n)[/math].[1]
- The above are close to optimal: The best possible revealment for balanced functions is [math]\Theta(n^{-1/2})[/math], and for monotone balanced functions it is [math]\Theta(n^{-1/3})[/math].[2]
References
- ↑ Theorem 1 in Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read by Benjamini, Schramm and Wilson.
- ↑ Theorem 2 in Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read by Benjamini, Schramm and Wilson.
