TAU Combinatorics Seminar 2022/23

When: Sunday, November 13, 10am
Speaker: Sahar Diskin, Tel Aviv University
Title: Supercritical Site Percolation on the Hypercube: Small components are small


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ás, Kohayakawa, and Ł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.