Expansion in the giant component of the percolated hypercube

Activity: Talk or presentationTalk at workshop, seminar or courseScience to science


As in the case of the binomial random graph, it is known that the behaviour of a random subgraph of a d-dimensional hypercube, where we include each edge independently with probability p, undergoes a phase transition when p is around 1/d. More precisely, answering a question of Erdős and Spencer, it was shown by Ajtai, Komlós and Szemerédi that significantly above this value of p, in the supercritical regime, whp this random subgraph has a unique 'giant' component, whose order is linear in the order of the hypercube. In the binomial random graph much more is known about the complex structure of this giant component, a lot of which can be deduced from more recent results about the likely expansion properties of the giant component. We show that whp the giant component L of a supercritical random subgraph of the d-dimensional hypercube has reasonably good expansion properties, and use this to deduce some structural information about L. In particular this leads to polynomial (in d) bounds on the diameter of L and the mixing times of a random walk on L, answering questions of Pete, and Bollobás, Kohayakawa, and Łuczak.
Period11 Aug 2021
Event titleBIRS workshop Random Graphs and Statistical Inference: New Methods and Applications
Event typeWorkshop
Conference number21w5108
LocationBannf, Canada, AlbertaShow on map
Degree of RecognitionInternational