Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

RSS-Feed




Revision #1
Authors: Eran Ofek
Accepted on: 26th October 2005 00:00
Downloads: 1826
Keywords: 


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}.


Paper:

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: 1748
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}$.



ISSN 1433-8092 | Imprint