Long paths and connectivity in 1-independent random graphs

DOI10.1002/RSA.20972zbMATH Open1454.05108arXiv1909.13771OpenAlexW3097258605WikidataQ104486762 ScholiaQ104486762MaRDI QIDQ3386526FDOQ3386526

Authors: A. Nicholas Day, Victor Falgas-Ravry, Robert Hancock 

Publication date: 5 January 2021

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: 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,geqslantp}(G)$ (resp. $mathcal{M}_{1,leqslantp}(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 $muinmathcal{M}_{1,geqslantp}(mathbb{Z}^2)$, $left(mathbfmathbb{Z}^{2}ight{)}_{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 $muinmathcal{M}_{1,geqslantp}(G)$ (resp. all $muinmathcal{M}_{1,leqslantp}(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.

Full work available at URL: https://arxiv.org/abs/1909.13771

Recommendations

• When are random graphs connected
• Critical probabilities of 1-independent percolation models
• On the connectedness of a random graph
• Extremal paths in inhomogenous random graphs
• scientific article; zbMATH DE number 4043893

zbMATH Keywords

extremal graph theorypercolationrandom graphslocal lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Probabilistic measure theory (60A10)

Cites Work

• Percolation
• Percolation
• Continuum Percolation
• Domination by product measures
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The critical probability of bond percolation on the square lattice equals 1/2
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random walks and percolation on trees
• Perturbing the hexagonal circle packing: a percolation perspective
• Continuum percolation with steps in the square or the disc
• On Dependency Graphs and the Lattice Gas
• Substitution Method Critical Probability Bounds for the Square Lattice Site Percolation Model
• Density conditions for triangles in multipartite graphs
• \(k\)-independent percolation on trees
• On 1-dependent processes and \(k\)-block factors
• An algebraic construction of a class of one-dependent processes
• Stable Poisson graphs in one dimension
• Percolation in invariant Poisson graphs with i.i.d. degrees
• A new lower bound for the critical probability of site percolation on the square lattice
• Rigorous confidence intervals on critical thresholds in 3 dimensions
• Runs in m-dependent sequences
• Finitely dependent coloring
• Upper bounds for the critical probability of oriented percolation in two dimensions
• On the critical value function in the divide and color model
• Complete subgraphs in multipartite graphs
• Percolation in the secrecy graph
• Critical probabilities of 1-independent percolation models
• Random transceiver networks

Cited In (5)

• Long Paths in Random Apollonian Networks
• On connectivity in random graph models with limited dependencies
• 1‐independent percolation on ℤ2×Kn
• Title not available (Why is that?)
• On density conditions for transversal trees in multipartite graphs

This page was built for publication: Long paths and connectivity in 1-independent random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386526)