# The phase transition in site percolation on pseudo-random graphs

Research paper by **Michael Krivelevich**

Indexed on: **05 Jul '15**Published on: **05 Jul '15**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

We establish the existence of the phase transition in site percolation on
pseudo-random $d$-regular graphs. Let $G=(V,E)$ be an $(n,d,\lambda)$-graph,
that is, a $d$-regular graph on $n$ vertices in which all eigenvalues of the
adjacency matrix, but the first one, are at most $\lambda$ in their absolute
values. Form a random subset $R$ of $V$ by putting every vertex $v\in V$ into
$R$ independently with probability $p$. Then for any small enough constant
$\epsilon>0$, if $p=\frac{1-\epsilon}{d}$, then with high probability all
connected components of the subgraph of $G$ induced by $R$ are of size at most
logarithmic in $n$, while for $p=\frac{1+\epsilon}{d}$, if the eigenvalue ratio
$\lambda/d$ is small enough as a function of $\epsilon$, then typically $R$
spans a connected component of size at least $\frac{\epsilon n}{d}$ and a path
of length proportional to $\frac{\epsilon^2n}{d}$.