Long paths and connectivity in 1‐independent random graphs. Issue 4 (16th October 2020)

• Record Type: Journal Article
• Authors: Day, A. Nicholas; Falgas‐Ravry, Victor; Hancock, Robert
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1007
• Page End: 1049
• Publication Date: 2020-10-16
• Subjects: extremal graph theory -- local lemma -- percolation -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20972
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : A probability measure μ on the subsets of the edge set of a graph G is a 1 ‐independent probability measure (1‐ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1‐ipm μ, denote by G μ the associated random graph model. Let ℳ 1, ⩾ p ( G ) denote the collection of 1‐ipms μ on G for which each edge is included in G μ with probability at least p . For G = Z 2, Balister and Bollobás asked for the value of the least p ⋆ such that for all p > p ⋆ and all μ ∈ ℳ 1, ⩾ p ( G ), G μ almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p ⋆ . We also determine the 1‐independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f 1, G ( p ), the infimum over all μ ∈ ℳ 1, ⩾ p ( G ) of the probability that G μ is connected. We determine f 1, G ( p ) exactly when G is a path, a complete graph and a cycle of length at most 5.