ECCC
Electronic Colloquium on Computational Complexity
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: 91
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: 85
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