On the expansion of the giant component in percolated (n,d,λ) graphs
| dc.creator | Ofek, Eran | |
| dc.date | 2005-09-12 | |
| dc.date | 2005-09-18 | |
| dc.date.accessioned | 2026-07-07T06:18:09Z | |
| dc.date.available | 2026-07-07T06:18:09Z | |
| dc.description | Let d \geq d_0 be a sufficiently large constant. A (n,d,c \sqrt{d}) graph G is a d-regular graph over n vertices whose second largest (in absolute value) eigenvalue is at most c \sqrt{d}. For any 0 < p < 1, G_p is the graph induced by retaining each edge of G with probability p. It is known that for p > \frac{1}{d} the graph G_p almost surely contains a unique giant component (a connected component with linear number vertices). We show that for p \geq frac{5c}{\sqrt{d}} the giant component of G_p almost surely has an edge expansion of at least \frac{1}{\log_2 n}. | |
| dc.identifier | https://arxiv.org/abs/math/0509253 | |
| dc.identifier | http://arxiv.org/abs/math/0509253 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94637 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | On the expansion of the giant component in percolated (n,d,λ) graphs | |
| dc.type | text |