Long paths and connectivity in 1-independent random graphs.

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.