Michael Krivelevich, Tel Aviv

Supercritical percolation on the hypercube-likely properties of the giant component
Mar 9, 2023, 4:30 pm5:30 pm


Event Description

A random subgraph of the binary d-dimensional hypercube Qd is one of the most classical and researched models of bond (edge) percolation. In this model, the base graph is the binary hypercube Qd(vertices are 0/1-vectors with d coordinates, two are adjacent if they differ in exactly one coordinate), and each edge of Qd 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+ϵ)/d, ϵ>0 a small constant, there is typically a unique component of size linear in |V(Qd)|=2d, 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.

Event Category
Probability Seminar