Supercritical percolation on the hypercube-likely properties of the giant component

-
Michael Krivelevich, Tel Aviv
Fine Hall 224

A random subgraph of the binary $d$-dimensional hypercube $Q^d$ is one of the most classical and researched models of bond (edge) percolation. In this model, the base graph is the binary hypercube $Q^d$ (vertices are $0/1$-vectors with d coordinates, two are adjacent if they differ in exactly one coordinate), and each edge of $Q^d$ is retained independently with probability $p=p(d)$.

It is known since the classical work of Ajtai, Komlos and Szemeredi in 1982 that the model undergoes phase transition at $p=1/d$, and in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ a small constant, there is typically a unique component of size linear in $|V(Q^d)|=2^d$, the so-called giant component.

We investigate typical combinatorial properties of the giant component, with an emphasis on, and a key being, its typical expansion. Among the properties we address are: edge- and vertex-expansion, diameter, length of a longest cycle, mixing time of a lazy random walk.

Our methods extend smoothly to the general setup of supercritical percolation on a product of many bounded size regular graphs.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.