Supercritical percolation on the hypercube-likely properties of the giant component
Supercritical percolation on the hypercube-likely properties of the giant component
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.