Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition

The BFW model introduced by Bohman, Frieze, and Wormald [Random Struct. Algorithms, 25, 432 (2004)], and recently investigated in the framework of discontinuous percolation by Chen and D'Souza [Phys. Rev. Lett. 106, 115701 (2011)], is studied on the square and simple-cubic lattices. In two and three dimensions, we find numerical evidence for a strongly discontinuous transition. In two dimensions, the clusters at the threshold are compact with a fractal surface of fractal dimension $d_f=1.49\pm 0.02$. On the simple-cubic lattice, distinct jumps in the size of the largest cluster are observed. We proceed to analyze the tree-like version of the model, where only merging bonds are sampled, for dimension two to seven. The transition is again discontinuous in any considered dimension. Finally, the dependence of the cluster-size distribution at the threshold on the spatial dimension is also investigated.

Figure 1

Fraction of sites in the largest cluster $P_{\infty }$ (solid red line), stage per site $k/N$ $(\circ )$, occupied bonds per step $t/u$ (dashed upper blue line), and $g\left(k\right)$ (dotted lower black line) as a function of the fraction of occupied bonds $p$, for the BFW model on the square lattice. As reported in Refs. [34, 36] for the random graph, $k$ is essentially equal to $s_{\max }$. Therefore, the corresponding curves in the figure, $P_{\infty }$ and $k/N$, almost overlap. The upper inset shows a close-up view of the upper-left corner of the main plot, as indicated by the box. The system size is $N={512}^2$, and the measured values are averages of over more than ${10}^5$ samples. In the lower inset we see the same variables as the main plot, measured for a single realization.

Figure 2

Fraction of sites in the largest cluster $P_{\infty }$ as a function of the fraction of occupied bonds $p$ on the square lattice for different lattice sizes $L$ (from left to right: 32, 64, 128, 256, 512, 1024, 2048, 4096, and 8192).

Figure 3

Snapshots of the system evolving according to the BFW model, obtained on a square lattice with ${512}^2$ sites. The following fractions of occupied bonds are shown: (a) $p=0.5$, (b) $0.9$, and (c) $0.95$. We note that in the thermodynamic limit $p_c$ seems to be equal to unity (see Fig. 10).

Figure 4

Order parameter $P_{\infty }$ $(*)$ immediately before the jump, jump size $J$ $(\square )$, and maximum of the second moment of the cluster-size distribution $M_2^{\prime }$ $(\circ )$ as a function of the linear system size $L$. All three quantities are asymptotically independent of the system size. For large system sizes, we estimate the following values: $J=0.415\pm 0.005$, $P_{\infty }=0.585\pm 0.005$, and $M_2^{\prime }=0.184\pm 0.006$. The solid lines represent the estimated mean value for each quantity. These results are clear signs for a discontinuous transition [24, 32, 39], as previously found for the random graph [34, 35].

Figure 5

$p_c-p_{c,X}$, with $p_c=1.000\pm 0.002$, as a function of the linear system size $L$ for the three estimators, the position of the jump $p_{c,J}$ $(\circ )$, the position $p_{c,M}$ $(*)$ of the maximum of $M_2^{\prime }$, and the point $p_{c,S}$ $(\square )$ at which spanning in one specific direction occurs. Asymptotically, we observe $(p_c-p_{c,X})\sim L^{-a}$ with $a=0.5\pm 0.2$.

Figure 6

Scaling plot for the standard deviation of the order parameter ${\chi }_{\infty }$ plotted as a function of the scaling variable $(p-p_c)L^a$, with $p_c=1$ and $a=0.5$, for different linear system sizes $L$ [32 $(▿)$, 64 $(\times )$, 128 $(*)$, 256 $(\square )$, 512 $\left(\blacksquare \right)$, 1024 $(\circ )$, 2048 $(•)$, 4096 $\left(▵\right)$, and 8192 $\left(▴\right)$]. Note that this value of the exponent $a$ agrees within error bars with the one obtained from the asymptotic behavior of $(p_c-p_{c,X})\sim L^{-a}$, $a=0.5\pm 0.2$; see Fig. 5. One observes that ${\chi }_{\infty }$ is nonzero in the thermodynamic limit, as expected for a discontinuous transition.

Figure 7

Size dependence of the number of interface bonds $A$ $(\circ )$. For large systems the interface size scales with the system size, $A\sim L^{d_f}.$ The straight line is a guide to the eye given by $0.824L^{1.47}$. In the lower right inset we see the local slopes $d_L=\log (A_L/A_{L/2})/\log \left(2\right)$ $(•)$ as function of the inverse system size $L^{-0.5}$. Extrapolating to $L\to \infty$ yields an exponent of $1.49\pm 0.02$. Box counting results are shown in the upper left inset: we see the rescaled number of occupied boxes $B{L}^{-d_f}$ as a function of the linear box size $n$ for two different system sizes: $L=8192$ ($\blacksquare$) and $L=4096$ ($\square$), the exponent is $1.49\pm 0.08$. Results have been averaged over ${10}^8$ samples for the smallest system size $\left({16}^2\right)$ and ${10}^3$ samples for the largest one $\left({8192}^2\right)$.

Figure 8

Fraction of sites in the largest cluster $P_{\infty }$ (solid red line), stage per site $k/N$ $(\circ )$, occupied bonds per step $t/u$ (dashed upper blue line), and $g\left(k\right)$ (dotted lower black line) as a function of the fraction of occupied bonds $p$, for the BFW model on the simple-cubic lattice. The system size is $N={64}^3$, the measured values are averages over ${10}^3$ samples. In the inset we see the same variables, measured for a single realization.

Figure 9

Fraction of sites in the largest cluster $P_{\infty }$ as a function of the fraction of occupied bonds $p$ on the simple-cubic lattice for different lattice sizes $L$ (from left to right: 8, 16, 32, 64, 128, 256, and 512).

Figure 10

Bond occupation fractions $p_{c,J,i}$ at which the six largest jumps in the order parameter occur for the BFW model as a function of the inverse system size, for (a) the square lattice and (b) the simple-cubic lattice. While for two dimensions all $p_{c,J,i}$ can be extrapolated to the same value $p_c=1.000\pm 0.002$, in three dimensions four distinct jumps are visible within error bars for $L\to \infty$ (compare also Fig. 8). For the square lattice, $a=0.5\pm 0.2$ and the solid line is a guide to the eye. On the simple-cubic lattice we find $p_{c,1}=0.756\pm 0.005$, $p_{c,2}=0.623\pm 0.007$, $p_{c,3}=0.578\pm 0.006$, and $p_{c,4}=0.539\pm 0.008$. For (b) results have been averaged over ${10}^8$ samples for the smallest system size $\left(8^3\right)$ and 40 samples for the largest one $\left({512}^3\right)$.

Figure 11

Maximum change $J$ in the order parameter in the BFW model on the simple-cubic lattice as a function of the fraction of occupied bonds $p$ for different linear system sizes $L$ [128 $(\square )$, 256 $(\circ )$, and 512 $\left(▵\right)$: peaks become narrower with increasing $L$]. The arrows indicate the positions of the four largest jumps, extrapolated to $L\to \infty$: $p=0.756$, $0.623$, $0.578$, and $0.539$ (see Fig. 10). The range between zero and unity for $p$ was divided into 512 bins of equal size and in every bin the maximum of the occurred changes in the order parameter was measured. Results have been averaged over $1.6\times {10}^5$ samples for the smallest system size $\left({128}^3\right)$ and $2.4\times {10}^3$ samples for the largest one $\left({512}^3\right)$.

Figure 12

Fraction of sites in the largest cluster $P_{\infty }$ as a function of the fraction of occupied bonds $p$ for (a) the tree-like BFW model and (b) tree-like classical percolation on hypercubic lattices of dimension two to seven (from right to left with increasing dimension). For the BFW model the transition is abrupt. In the classical case, the transition is continuous and the thresholds are compatible with results for the number of clusters at the critical point [57, 58, 59]. The insets show the fraction of sites $s/N$ in the three largest clusters [1st ($\square$, upper curve), 2nd ($▵$, middle curve), and 3rd ($\circ$, lower curve)] as a function of the fraction of occupied bonds $p$ for single typical realizations of (a) the tree-like BFW model and (b) tree-like classical percolation on the hypercubic lattice of dimension seven of size $6^7$. While for the BFW model the largest cluster grows by overtaking, i. e., the second largest cluster overtakes the largest one which becomes the second largest one, for classical percolation the largest cluster grows directly by merging with smaller clusters. For the main plots, the system sizes $L^d$ are ${2048}^2$, ${161}^3$, ${45}^4$, ${21}^5$, ${13}^6$, and $9^7$ for both models. Results have been averaged over at least $2\times {10}^3$ samples.

Figure 13

Percolation threshold estimator $p_c-p_{c,J}$ as a function of the inverse system size $N^{-1}$ for the tree-like BFW model on the hypercubic lattice of dimensions two to seven. Extrapolating to $L\to \infty$, we find $p_c=0.500\pm 0.001$, $0.333\pm 0.002$, $0.248\pm 0.002$, $0.198\pm 0.003$, $0.165\pm 0.004$, and $0.141\pm 0.009$. Note that $p_c$ seems to be $1/d$. In the inset we see the same data for $p_c-p_{c,J}$, plotted as a function of $N=L^d$ in double-logarithmic scale, where the solid line is a guide to the eye of the form $0.018N^{-0.7}$. Results have been averaged over at least $7.8\times {10}^6$ samples for the smallest system size (${64}^2$, ${16}^3$, $8^4$, $5^5$, $4^6$, and $4^7$) and over at least 100 samples for the largest one (${8192}^2$, ${512}^3$, ${91}^4$, ${37}^5$, ${20}^6$, and ${16}^7$).

Figure 14

The largest change in the order parameter: $J$ is plotted as a function of $N=L^d$ for the tree-like BFW model on hypercubic lattices of dimension two to seven. Asymptotically, the jump is independent on system size, indicating a strongly discontinuous transition. The solid lines are guides to the eye indicating the following constant values: $0.415\pm 0.005$, $0.414\pm 0.002$, $0.412\pm 0.003$, $0.410\pm 0.003$, $0.409\pm 0.002$, and $0.409\pm 0.002$, for dimension two to seven.

Figure 15

Accumulated cluster-size distribution $N_s$ as a function of the cluster size $s$ for the tree-like BFW model on hypercubic lattices of dimension three $(\blacksquare ,\square )$, five $(▴,▵)$, and seven $(▾,▿)$. $N_s={\sum }_{r=s}^{2s-1}{n}_r$, where $n_s$ is the number of clusters of size $s$ per lattice site $N=L^d$, excluding the largest cluster of size $s_{\max }$. One observes that the distribution falls off sharply for small cluster sizes and has a region on the right, qualitatively similar to the behavior on the random graph [34, 35]. For comparison, the inset shows $N_s$ as a function of $s$ for tree-like classical percolation on the square lattice at $p_c=(7-3\sqrt{3})/4$ [57, 58, 59]. Results are shown for system sizes of ${8192}^2$ $(\circ )$ and ${16384}^2$ $(•)$. Asymptotically, the points follow a power law, $N_s\sim s^{1-\tau }$, where $\tau =187/91$. All results have been averaged over 100 samples.