Vertex Percolation on Expander Graphs
| dc.creator | Ben-Shimon, Sonny | |
| dc.creator | Krivelevich, Michael | |
| dc.date | 2007-10-11 | |
| dc.date | 2008-07-01 | |
| dc.date.accessioned | 2026-07-07T12:05:10Z | |
| dc.date.available | 2026-07-07T12:05:10Z | |
| dc.description | We say that a graph $G=(V,E)$ on $n$ vertices is a $β$-expander for some constant $β>0$ if every $U\subseteq V$ of cardinality $|U|\leq \frac{n}{2}$ satisfies $|N_G(U)|\geq β|U|$ 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^{-α}$ for some constant $α>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,λ)$-graphs, that are such expanders, we compute the values of $α$, 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. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0710.2296 | |
| dc.identifier | http://arxiv.org/abs/0710.2296 | |
| dc.identifier | European Journal of Combinatorics, 30(2), pp. 339-350, 2009 | |
| dc.identifier | doi:10.1016/j.ejc.2008.07.001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/208305 | |
| dc.subject | Combinatorics | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Probability | |
| dc.title | Vertex Percolation on Expander Graphs | |
| dc.type | text |