Talk information

Date: Sunday, April 26, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Itay Markbreit (Tel Aviv University)
Title: Supercritical site percolation on regular graphs

Abstract:

Given a host graph $G = (V, E)$ and probability $p \in [0, 1]$, in site (vertex) percolation we form a random subset $V_p \subseteq V$ by including each vertex $v \in V$ in $V_p$ independently and with probability $p$, and analyze the subgraph $G[V_p]$. In this talk, we consider site percolation on $d$-regular graphs, for the growing-degree case. We give sufficient, and relatively tight, conditions for the emergence of the “Erdős–Rényi component phenomenon” in the supercritical regime $p = (1+\varepsilon)/d$ : namely, the likely appearance of a unique giant component of order $n/d$ in the percolated subgraph, with all other components being of size $O(\log n)$. The main results apply both to the $d$-dimensional hypercube and to pseudo-random graphs, and resolve two open questions in these cases.

A joint work with Sahar Diskin and Michael Krivelevich.