Extended butterfly percolation

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}[/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].
• 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].