Talk information

Date: Sunday, November 13, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Sahar Diskin (TAU)
Title: Supercritical Site Percolation on the Hypercube: Small Components Are Small

Abstract:

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. In this talk, we consider site percolation on the d-dimensional hypercube $Q^d$ in the supercritical regime, that is, with probability $p=\frac{1+\epsilon}{d}$. In 1994, Bollob'as, Kohayakawa, and \L{}uczak showed that the largest component of $Q^d[R]$ in this regime is typically of size $\Theta(2^d/d)$, and that with high probability, all the other components are of order $O(d^{10})$. They conjectured that, with high probability, all the components besides the largest one are in fact of size $O(d)$ (note that $O(d)=O(\log |V(Q^d)|)$ is optimal, and at large analogous to the case of supercritical $G(n,p)$). We resolve their conjecture, showing that in the supercritical regime, typically all the components of $Q^d[R]$ besides the largest one are of size $O(d)$.

Joint work with Michael Krivelevich.