pith. sign in

arxiv: 1605.06643 · v2 · pith:PZ2MMJQWnew · submitted 2016-05-21 · 🧮 math.CO

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

classification 🧮 math.CO
keywords alphacomponentsizegiantlambdathenabsoluteadjacency
0
0 comments X
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.