The computation of generalized percolation critical polynomials by the deletion-contraction algorithm

Abstract

Although every exactly known bond percolation critical threshold is the root in $[0,1]$ of a lattice-dependent polynomial, it has recently been shown that the notion of a critical polynomial can be extended to any periodic lattice. The polynomial is computed on a finite subgraph, called the base, of an infinite lattice. For any problem with exactly known solution, the prediction of the bond threshold is always correct, regardless of the base chosen. For unsolved problems, the polynomial is referred to as the generalized critical polynomial and provides an approximation that becomes more accurate with increasing number of bonds in the base, appearing to approach the exact answer. The polynomials are computed using the deletion-contraction algorithm, which quickly becomes intractable by hand for more than about 18 bonds. Here, I present generalized critical polynomials calculated with a computer program for bases of up to 36 bonds for all the Archimedean lattices, except the kagome which was considered in an earlier work. The polynomial estimates are generally within $10^{-5}$ to $10^{-7}$ of the numerical values, but the prediction for the $(4,8^2)$ lattice, though not exact, is not ruled out by simulations.

References in corpus (6)

• Exact bond percolation thresholds in two dimensions
• Estimation of Bond Percolation Thresholds on the Archimedean Lattices
• Critical surfaces for general bond percolation problems
• Rigorous confidence intervals for critical probabilities
• Critical frontier for the Potts and percolation models on triangular-type and kagome-type lattices II: Numerical analysis
• The percolation critical polynomial as a graph invariant

Cited by in corpus (3)

• Transfer matrix computation of critical polynomials for two-dimensional Potts models
• Phase diagram of the triangular-lattice Potts antiferromagnet
• Exact percolation probabilities for a square lattice: Site percolation on a plane, cylinder, and torus