EXPANSION IN SUPERCRITICAL RANDOM SUBGRAPHS OF THE HYPERCUBE AND ITS CONSEQUENCES

• 成果类型: Article
• 署名作者: Erde, J. O. S. H. U. A.; Kang, M. I. H. Y. U. N.; Krivelevich, M. I. C. H. A. E. L.
• 署名单位: Graz University of Technology; Tel Aviv University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/22-AOP1592
• 发表日期: 2023
• 页码: 127-156
• 关键词: diameter; graphs; EVOLUTION; percolation; expanders; component; numbers

摘要

It is well 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, standard arguments show that just below this value of p all components of this graph have order O(d) with probability tending to one as d -> infinity (whp for short), whereas Ajtai, Komlos and Szemeredi (Combinatorica 2 (1982) 1-7) showed that just above this value, in the supercritical regime, whp there is a unique giant component of order Theta(2(d)). We show that whp the vertex expansion of the giant component is inverse polynomial in d. As a consequence, we obtain polynomial in d bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component, answering questions of Bollobas, Kohayakawa and Luczak (Random Structures and Algorithms 5 (1994) 627-648) and of Pete (Electron. Commun. Probab. 13 (2008) 377-392). Furthermore, our results imply lower bounds on the circumference and Hadwiger number of a random subgraph of the hypercube in this regime of p, which are tight up to polynomial factors in d.