Premium
Long paths and connectivity in 1‐independent random graphs
Author(s) -
Day A. Nicholas,
FalgasRavry Victor,
Hancock Robert
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20972
Subject(s) - combinatorics , mathematics , infimum and supremum , random graph , discrete mathematics , probability measure , graph , random regular graph , measure (data warehouse) , path (computing) , line graph , 1 planar graph , computer science , programming language , database
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 byG μthe associated random graph model. Letℳ 1 , ⩾ p ( G ) denote the collection of 1‐ipms μ on G for which each edge is included inG μ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 thatG μ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.