Given a graph $G$, a probability measure $\mu$ on the subsets of the edge set of $G$ is said to be $1$-independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$-ipm on $G$, and denote by $\mathbf{ G}_{ \mu}$ the associated random spanning subgraph of $G$. Let $\mathcal{ M}_{ 1,\geqslant p}(G)$ (resp. $\mathcal{ M}_{ 1,\leqslant p}(G)$) denote the collection of $1$-ipms $\mu$ on $G$ for which each edge is included in $\mathbf{ G}_{ \mu}$ with probability at least $p$ (resp. at most $p$). Let $\mathbb{ Z}^2$ denote the square integer lattice. Balister and Bollob\'as raised the question of determining the critical value $p_{ \star}=p_{ 1,c}(\mathbb{ Z}^2)$ such that for all $p>p_{ \star}$ and all $\mu \in \mathcal{ M}_{ 1,\geqslant p}(\mathbb{ Z}^2)$, $\left(\mathbf{ \mathbb{ Z}^2}\right)_{ \mu}$ almost surely contains an infinite component. This can be thought of as asking for a $1$-independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$-ipms more generally. We give two lower bounds on $p_{ \star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$-independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{ 1,G}(p)$ (respectively $F_{ 1,G}(p)$), the infimum (resp. supremum) over all $\mu\in \mathcal{ M}_{ 1,\geqslant p}(G)$ (resp. all $\mu \in \mathcal{ M}_{ 1,\leqslant p}(G)$) of the probability that $\mathbf{ G}_{ \mu}$ is connected. We determine $f_{ 1,G}(p)$ and $F_{ 1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$. Many new problems arise from our work, which are discussed in the final section of the paper.
Categories: math.PR math.CO