2014/04/23 by Michael Krivelevich, Krivelevich, Michael · 2 citations
Mathematics · #05C80 #82B43 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05C80 #msc:82B43
paper · pdf · doi:10.48550/arxiv.1404.5731
arXiv admin note: text overlap with arXiv:1201.6529
openalex publication_date 2014/04/23 · arxiv created 2015/07/05 · arxiv updated 2015/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We establish the existence of the phase transition in site percolation on pseudo-random d-regular graphs. Let G=(V,E) be an (n,d,λ)-graph, that is, a d-regular graph on n vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most λ in their absolute values. Form a random subset R of V by putting every vertex v∈ V into R independently with probability p. Then for any small enough constant ε>0, if p=(1-ε)/(d), then with high probability all connected components of the subgraph of G induced by R are of size at most logarithmic in n, while for p=(1+ε)/(d), if the eigenvalue ratio λ/d is small enough as a function of ε, then typically R spans a connected component of size at least (εn)/(d) and a path of length proportional to (ε2n)/(d).