Long paths and connectivity in 1-independent random graphs

DOI10.1002/RSA.20972MaRDI QIDQ3386526zbMATH OpenOpenAlexWikidataFDO

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

Publication date 5 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(5)

• Long Paths in Random Apollonian Networks
• On connectivity in random graph models with limited dependencies
• 1‐independent percolation on ℤ2×Kn
• scientific article; zbMATH DE number 3915301 (Why is no real title available?)
• 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)