ECCC-Report TR05-112https://eccc.weizmann.ac.il/report/2005/112Comments and Revisions published for TR05-112en-usWed, 26 Oct 2005 00:00:00 +0200
Revision 1
| On the expansion of the giant component in percolated (n,d,\lambda) graphs Revision of: TR05-112 |
Eran Ofek
https://eccc.weizmann.ac.il/report/2005/112#revision1Let 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}.
Wed, 26 Oct 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2005/112#revision1
Paper TR05-112
| On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs |
Eran Ofek
https://eccc.weizmann.ac.il/report/2005/112Let $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}$.
Sat, 08 Oct 2005 20:02:36 +0300https://eccc.weizmann.ac.il/report/2005/112