BIMSA >
Research seminar in Discrete Mathematics
Diameter and mixing time of the giant component in the percolated hypercube
Diameter and mixing time of the giant component in the percolated hypercube
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
Lyuben Lichev
Time
Tuesday, December 2, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
The d-dimensional binary hypercube is the graph whose vertices represent the binary vectors of length d and two vertices are adjacent if they differ in a single coordinate. The percolated hypercube (where every edge is retained independently with probability p) is a classic model in random graph theory. In this talk, we are going to survey some of the history of the model and discuss recent estimates of the mixing time of the lazy simple random walk on the giant component and of the diameter of the giant component in a supercritical percolated hypercube. Based on a joint work with Michael Anastos, Sahar Diskin and Maksim Zhukovskii.