The emergence of a giant component in random subgraphs of pseudo-random graphs

Abstract

Let $G$ be a $d$-regular graph $G$ on $n$ vertices. Suppose that the adjacency matrix of $G$ is such that the eigenvalue $\lambda$ which is second largest in absolute value satisfies $\lambda =o(d)$. Let $G_p$ with $p=\frac{\alpha }{d}$ be obtained from $G$ by including each edge of $G$ independently with probability $p$. We show that if $\alpha <1$ then whp the maximum component size of $G_p$ is $O(\log n)$ and if $\alpha >1$ then $G_p$ contains a unique giant component of size $\Omega (n)$, with all other components of size $O(\log n)$.

9 pages

Cited by in corpus (3)

• A geometric entropy detecting the Erdös-Rényi phase transition
• Spectrum of Johnson graphs
• Vertex Percolation on Expander Graphs