2021/11/12 by Joshua Erde, Erde, Joshua, Mihyun Kang +3 · 1 citation
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2111.06752
It is well-known that the behaviour of a random subgraph of a d-dimensional\nhypercube, where we include each edge independently with probability p,\nundergoes a phase transition when p is around \(1)/(d). More precisely,\nstandard arguments show that just below this value of p all components of\nthis graph have order O(d) with probability tending to one as d \→ \∞\n(whp for short), whereas Ajtai, Koml 'os and Szemer 'edi [Largest random\ncomponent of a k-cube, Combinatorica 2 (1982), no. 1, 1--7; MR0671140] showed\nthat just above this value, in the supercritical regime, whp there is a unique\n`giant' component of order \Θ\(2d\). We show that whp the\nvertex-expansion of the giant component is inverse polynomial in d. As a\nconsequence we obtain polynomial in d bounds on the diameter of the giant\ncomponent and the mixing time of the lazy random walk on the giant component,\nanswering questions of Bollob 'as, Kohayakawa and Luczak [On the diameter\nand radius of random subgraphs of the cube, Random Structures and Algorithms 5\n(1994), no. 5, 627--648; MR1300592] and of Pete [A note on percolation on\n\ℤd: isoperimetric profile via exponential cluster repulsion,\nElectron. Commun. Probab. 13 (2008), 377--392; MR2415145]. Furthermore, our\nresults imply lower bounds on the circumference and Hadwiger number of a random\nsubgraph of the hypercube in this regime of p which are tight up to\npolynomial factors in d.\n