The emergence of a giant component in random subgraphs of pseudo-random graphs
classification
🧮 math.CO
keywords
alphacomponentsizegiantlambdathenabsoluteadjacency
read the original 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)$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.