Long paths and connectivity in 1‐independent random graphs

A probability measure [Formula: see text] 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 [Formula: see text] , denote by [Formula: see text] the associated random graph model. Let [Formula: see text] denote the collection of 1‐ipms [Formula: see text] on G for which each edge is included in [Formula: see text] with probability at least p. For [Formula: see text] , Balister and Bollobás asked for the value of the least p (⋆) such that for all p > p (⋆) and all [Formula: see text] , [Formula: see text] 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 [Formula: see text] of the probability that [Formula: see text] 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.