__
Revision #1 to TR05-112 | 26th October 2005 00:00
__
#### On the expansion of the giant component in percolated (n,d,\lambda) graphs Revision of: TR05-112

**Abstract:**
Let d > 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}.

__
TR05-112 | 12th September 2005 00:00
__

#### On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

TR05-112
Authors:

Eran Ofek
Publication: 8th October 2005 20:02

Downloads: 1364

Keywords:

**Abstract:**
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 eigenvalue (in absolute value) 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$. We show that for

any $p > \frac{5c}{\sqrt{d}}$ the graph $G_p$ almost surely contains

a unique giant component (a connected component with linear number

vertices). We further show that the giant component of $G_p$ almost

surely has an edge expansion of at least $\frac{1}{\log_2 n}$.