Exactly solvable percolation problems

We propose a simple percolation criterion for arbitrary percolation problems. The basic idea is to decompose the system of interest into a hierarchy of neighborhoods, such that the percolation problem can be expressed as a branching process. The criterion provides the exact percolation thresholds for a large number of exactly solved percolation problems, including random graphs, small-world networks, bond percolation on two-dimensional lattices with a triangular hypergraph, and site percolation on two-dimensional lattices with a generalized triangular hypergraph, as well as specific continuum percolation problems. The fact that the range of applicability of the criterion is so large bears the remarkable implication that all the listed problems are effectively treelike. With this in mind, we transfer the exact solutions known from duality to random lattices and site-bond percolation problems and introduce a method to generate simple planar lattices with a prescribed percolation threshold.

Figure 1

Depiction of the vertex decomposition ${\left(V_k\right)}_{k\in \mathbb{N}}$. All panels illustrate the 3-neighborhood of the origin; the top panels show the square lattice, and the bottom panels show the triangular lattice. In the left panels all edges are drawn, while the right panels show a specific configuration of the lattice displaying only open edges. The numbers on the vertices correspond to the index $k$ of the associated vertex set $V_k$. On the right only vertices contributing to the surface activity are given a number.

Figure 2

The transition from $V_k$ (circles and triangles) to $V_{k+1}$ (squares) on the square lattice. There are two different types of local environments depicted by different shapes: Circles have two shared neighbors on the subsequent layer, while triangles have an additional exclusive neighbor.

Figure 3

Left: Asymptotic substitute lattice for the square lattice. Right: Bethe lattice with identical average surface (gray shading) activity at the percolation threshold.

Figure 4

The average activity of the $k\mathrm{th}$ layer of the asymptotic substitute of the square lattice. Lines represent analytic results, while the symbols are simulation results.

Figure 5

$Q_1$ with the square lattice unit cell attached to each vertex in $V_1^{\prime }$. In order to recover $Q_2$ the white vertices have to be contracted. The sum of paths connecting the root node to each of the leaf nodes individually is invariant under this vertex contraction.

Figure 6

Left: Asymptotic substitute lattice for the triangular lattice. Right: Triangular tree lattice; its percolation threshold corresponds to a correlated triangular lattice.

Figure 7

Top: A pseudorandom network created from a triangular hypergraph filled with unit cells of square, triangular, and hexagonal lattices with equal probability. Bottom: Simulation results for lattices of the kind above with periodic boundary conditions sampling the graph polynomial, with ${\mathrm{\Theta }}_2$ and ${\mathrm{\Theta }}_0$ being the probabilities of obtaining a two-dimensional wrapping cluster or no wrapping cluster, respectively.

Figure 8

Snippets of lattices created from triangular and square unit cells in equal proportion: elongated triangular lattice, $p_c\approx 0.4196$ (nonexact; left), bow-tie lattice, $p_c\approx 0.4045$ (exact; middle), and random alignment, $p_c=\sqrt{2}-1\approx 0.4142$ (exact; right).

Figure 9

Nonplanar unit cells embedded in the triangular hypergraph at the black vertices are exactly solvable: $K_5$: $p_c\approx 0.2528$; $K_{3,3}$: $p_c\approx 0.3903$.

Figure 10

Our exactly solvable site percolation problems. Left: Elongated kagome, $p^2+2p^3-p^4=1 \to p_c\approx 0.7213$. Right: Clinched 3-12, $2p^3+p^4-p^5=1 \to p_c\approx 0.7717$.

Figure 11

Left: Kagome lattice with fixed edges (dashed red lines). Right: Critical manifold for site-bond percolation for the lattice on the left. Symbols denote simulation results, the solid line represents solutions to Eq. (34), and the dashed line is an approximation due to [36].