Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

Percolation on Bidirected Graphs

  • Yucheng Liu
  • Leonardo T. Rolla
  • Yuliang Shi
Open at sourcePDFDOICite

Abstract

We study bidirected percolation on an undirected graph G: each edge is replaced by two oppositely directed edges, each of which is open independently with probability p. Two vertices are strongly connected if they are mutually reachable by open directed paths. Let psc denote the threshold for the existence of an infinite strongly connected cluster, and let pc denote the usual Bernoulli percolation threshold on G. On every transitive amenable graph, we prove that psc=pc. In contrast, sufficiently spread-out modifications of every transitive non-amenable graph satisfy psc>pc. We also show that, on ℤd with d≥11, the expected size of the strongly connected cluster is finite at p=psc.

Related

  1. Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs
    Roman Vasquez
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Locality of Bernoulli Site Percolation on Transitive Graphs
    Tho Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  3. Percolation on Finite Graphs
    Michael Krivelevich
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
    Joel Bassil
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  5. 2-Neighbor Bootstrap Percolation on Odd Graphs
    Ali Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026percolation,
  title = {{Percolation on Bidirected Graphs}},
  author = {Yucheng Liu and Leonardo T. Rolla and Yuliang Shi},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.28762},
  eprint = {2610.28762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.28762},
}
RIS
TY  - UNPB
TI  - Percolation on Bidirected Graphs
AU  - Yucheng Liu
AU  - Leonardo T. Rolla
AU  - Yuliang Shi
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.28762
UR  - https://arxiv.org/abs/2610.28762
AB  - We study bidirected percolation on an undirected graph G: each edge is replaced by two oppositely directed edges, each of which is open independently with probability p. Two vertices are strongly connected if they are mutually reachable by open directed paths. Let p_sc denote the threshold for the existence of an infinite strongly connected cluster, and let p_c denote the usual Bernoulli percolation threshold on G. On every transitive amenable graph, we prove that p_sc=p_c. In contrast, sufficiently spread-out modifications of every transitive non-amenable graph satisfy p_sc>p_c. We also show that, on ℤ^d with d≥11, the expected size of the strongly connected cluster is finite at p=p_sc.
ER  -