1-independent percolation on ℤ2×Kn

Victor Falgas-Ravry*, Vincent Pfenninger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)887– 910
Number of pages24
JournalRandom Structures and Algorithms
Volume62
Issue number4
Early online date21 Dec 2022
DOIs
Publication statusPublished - 22 May 2023

Fingerprint

Dive into the research topics of '1-independent percolation on ℤ2×Kn'. Together they form a unique fingerprint.

Cite this