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=(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=(1+\epsilon )/d$, if

the eigenvalue ratio $\lambda /d$ is small enough as a function of $\epsilon$, then typically $R$ contains a connected component of size at least

$\epsilon n/d$ and a path of length proportional to $\epsilon^2n/d$.

# The Phase Transition in Site Percolation on Pseudo-Random Graphs

Event time:

Thursday, February 12, 2015 - 11:00am to 12:00pm

Location:

215 LOM

Speaker:

M. Krivelevich

Speaker affiliation:

Tel Aviv

Event description: