TAU Combinatorics Seminar 2021/22

When: Sunday, November 14, 10am
Speaker: Sahar Diskin, Tel Aviv University
Title: Site percolation on pseudo-random graphs


In the site percolation model, a random induced subgraph $G[R]$ of a given graph $G$ is formed by putting every vertex $v$ of $G$ into a random subset $R$ with probability $p$ and independently. One then researches typical properties of $G[R]$, like the sizes of its connected components.

Here we study site percolation on pseudo-random graphs, specifically on $(n,d,\lambda)$-graphs, which are $d$-regular graphs on $n$ vertices with all eigenvalues but the first (trivial) one bounded in absolute values by $\lambda$. It is well known that, assuming that the eigenvalue ratio $\lambda/d$ is small, the edge distribution of an $(n,d,\lambda)$-graph resembles closely that of a truly random graph $G(n,p)$ with the same expected density $p=d/n$.

We focus on the so-called supercritical regime $p=\frac{1+\epsilon}{d}$, for a positive constant $\epsilon>0$. In this range, we establish the asymptotic order of the giant component (a component of size proportional to $|R|$) in $G[R]$ and show that it is typically unique. We also discuss further properties of the giant.

A joint work with Michael Krivelevich.