Vertex percolation on expander graphs

DOI10.1016/J.EJC.2008.07.001zbMATH Open1215.05155arXiv0710.2296OpenAlexW2124886183MaRDI QIDQ1003582FDOQ1003582

Authors: Sonny Ben-Shimon, Michael Krivelevich 

Publication date: 4 March 2009

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We say that a graph $G=(V,E)$ on $n$ vertices is a $$-expander for some constant $$ if every $UsubseteqV$ of cardinality $|U|leqfracn2$ satisfies $$ where $N_G(U)$ denotes the neighborhood of $U$. In this work we explore the process of deleting vertices of a $$-expander independently at random with probability $n^{-alpha}$ for some constant $alpha>0$, and study the properties of the resulting graph. Our main result states that as $n$ tends to infinity, the deletion process performed on a $$-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing $n-o(n)$ vertices that is in itself an expander graph, and constant size components. We proceed by applying the main result to expander graphs with a positive spectral gap. In the particular case of $(n,d,lambda)$-graphs, that are such expanders, we compute the values of $alpha$, under additional constraints on the graph, for which with high probability the resulting graph will stay connected, or will be composed of a giant component and isolated vertices. As a graph sampled from the uniform probability space of $d$-regular graphs with high probability is an expander and meets the additional constraints, this result strengthens a recent result due to Greenhill, Holt and Wormald about vertex percolation on random $d$-regular graphs. We conclude by showing that performing the above described deletion process on graphs that expand sub-linear sets by an unbounded expansion ratio, with high probability results in a connected expander graph.

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

Recommendations

• Expansion properties of a random regular graph after random vertex deletions
• Expander properties in random regular graphs with edge faults
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
• The sharp threshold for percolation on expander graphs
• Sharp threshold for percolation on expanders

zbMATH Keywords

\(\beta\)-expander

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Expander graphs and their applications
• Title not available (Why is that?)
• A proof of Alon’s second eigenvalue conjecture and related problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pseudo-random graphs
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Percolation on finite graphs and isoperimetric inequalities.
• The emergence of a giant component in random subgraphs of pseudo-random graphs
• Mean-field conditions for percolation on finite graphs
• Expansion properties of a random regular graph after random vertex deletions
• Scalable secure storage when half the system is faulty

Cited In (4)

• The sharp threshold for percolation on expander graphs
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
• Expansion of Percolation Critical Points for Hamming Graphs
• Expansion properties of a random regular graph after random vertex deletions

This page was built for publication: Vertex percolation on expander graphs

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