Abstract
A random graph model on a host graph H is said to be 1-independent if for every pair of vertex-disjoint subsets A,B of E(H), the state of edges (absent or present) in A is independent of the state of edges in B. For an infinite connected graph H, the 1-independent critical percolation probability p1,c(H) is the infimum of the p∈[0,1] such that every 1-independent random graph model on H in which each edge is present with probability at least p almost surely contains an infinite connected component. Balister and Bollobás observed in 2012 that p1,c(ℤd) tends to a limit in [1/2,1] as d→∞, and they asked for the value of this limit. We make progress on a related problem by showing that limn→∞
p1,c(ℤ2×Kn) = 4−2√3 = 0.5358…. In fact, we show that the equality above remains true if the sequence of complete graphs Kn is replaced by a sequence of weakly pseudorandom graphs on n vertices with average degree ω(logn). We conjecture the answer to Balister and Bollobás's question is also 4−2√3.
p1,c(ℤ2×Kn) = 4−2√3 = 0.5358…. In fact, we show that the equality above remains true if the sequence of complete graphs Kn is replaced by a sequence of weakly pseudorandom graphs on n vertices with average degree ω(logn). We conjecture the answer to Balister and Bollobás's question is also 4−2√3.
Original language | English |
---|---|
Pages (from-to) | 887– 910 |
Number of pages | 24 |
Journal | Random Structures and Algorithms |
Volume | 62 |
Issue number | 4 |
Early online date | 21 Dec 2022 |
DOIs | |
Publication status | Published - 22 May 2023 |