Asymptotics in percolation on high-girth expanders

DOI10.1002/RSA.20903MaRDI QIDQ5128747zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

Publication date 26 October 2020

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

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

zbMATH Keywords

bond percolationcomponent sizesgiant componenthigh-girth expanders

Mathematics Subject Classification ID

Distance in graphs (05C12) Density (toughness, etc.) (05C42) Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider supercritical bond percolation on a family of high-girth $d$-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized ("giant) component is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2-core at any $p>p_c$. It was further shown in [ABS04] that the second largest component, at any $0<p<1$, has size at most $n^{omega}$ for some $omega<1$. We show that, unlike the situation in the classical ErdH{o}s-R'enyi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{omeg{a}^{\prime }}$ for $omeg{a}^{\prime }$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path.

Recommendations

• Percolation on finite graphs and isoperimetric inequalities.
• Sharp threshold for percolation on expanders
• Critical percolation on random regular graphs
• The sharp threshold for percolation on expander graphs
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs

Cites work

• Anatomy of a Young giant component in the random graph
• Anatomy of the giant component: the strictly supercritical regime
• Critical percolation on random regular graphs
• Edge percolation on a random regular graph of low degree
• Euclidean vs. Graph Metric
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2119076 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Is the critical percolation probability local?
• Long paths and Hamiltonicity in random graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Random graphs and complex networks. Volume 1
• Random graphs.
• Random minimum length spanning trees in regular graphs

Cited in

(17)

• Percolation on finite graphs and isoperimetric inequalities.
• Level-set percolation of the Gaussian free field on regular graphs II: finite expanders
• Crux and Long Cycles in Graphs
• Arm exponents in high dimensional percolation
• The sharp threshold for percolation on expander graphs
• Giant component for the supercritical level‐set percolation of the Gaussian free field on regular expander graphs
• Site percolation on pseudo‐random graphs
• Locality of random digraphs on expanders
• Metastability of the Potts ferromagnet on random regular graphs
• Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs
• Expansion in supercritical random subgraphs of expanders and its consequences
• Percolation on irregular high-dimensional product graphs
• Sharpness and locality for percolation on finite transitive graphs
• Components, large and small, are as they should be. II: Supercritical percolation on regular graphs of constant degree
• Non-triviality of the phase transition for percolation on finite transitive graphs
• Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
• Percolation on preferential attachment models

This page was built for publication: Asymptotics in percolation on high-girth expanders

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