Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 14 min ago
PreprintCC BY 4.0arXiv

Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs

  • Joel Bassil
Open at sourcePDFDOICite

Abstract

We consider site percolation on general graphs and give a sufficient condition on the escape probability of a certain random walk with degree-dependent conductances, such that the number of minimal vertex cutsets of size n separating a given vertex from infinity is bounded above exponentially in n. This result extends an analogous theorem of Easo, Severo and Tassion under slightly stronger assumptions. Moreover, we give an alternative sufficient condition in terms of the isoperimetric dimension or, more specifically, an isoperimetric-type inequality. Furthermore, our theorem is sufficient to extend the results of Panagiotis and Severo, and show that there exists a universal positive constant ε1 such that site percolation on every infinite, connected, locally finite, vertex-transitive graph satisfies pc = 1 or pc ≤ 1−ε1.

Related

  1. Locality of Bernoulli Site Percolation on Transitive Graphs
    Tho Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
    Zejun Huang, Chenxi Yang
    HALPreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL
  3. Vertex-transitive strongly regular graphs in the switching class of doubly transitive two-graphs
    Robert F. Bailey, Gábor P. Nagy, Valentino Smaldore
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Enumeration of small vertex-transitive directed strongly regular graphs
    A. E. Brouwer, Š. Gyürki
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Linear circumference in vertex-transitive graphs
    Jie Ma, Ziyuan Zhao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bassil2026counting,
  title = {{Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs}},
  author = {Joel Bassil},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08261},
  eprint = {2610.08261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08261},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
AU  - Joel Bassil
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.08261
UR  - https://arxiv.org/abs/2610.08261
AB  - We consider site percolation on general graphs and give a sufficient condition on the escape probability of a certain random walk with degree-dependent conductances, such that the number of minimal vertex cutsets of size n separating a given vertex from infinity is bounded above exponentially in n. This result extends an analogous theorem of Easo, Severo and Tassion under slightly stronger assumptions. Moreover, we give an alternative sufficient condition in terms of the isoperimetric dimension or, more specifically, an isoperimetric-type inequality. Furthermore, our theorem is sufficient to extend the results of Panagiotis and Severo, and show that there exists a universal positive constant ε_1 such that site percolation on every infinite, connected, locally finite, vertex-transitive graph satisfies p_c = 1 or p_c ≤ 1−ε_1.
ER  -