Sandwiching dense random regular graphs between binomial random graphs

• 成果类型: Article
• 署名作者: Gao, Pu; Isaev, Mikhail; McKay, Brendan D.
• 署名单位: University of Waterloo; Monash University; Australian National University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01157-6
• 发表日期: 2022
• 页码: 115-158
• 关键词: NUMBER

摘要

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d >> log n, then the random d-regular graph G(n, d) can asymptotically almost surely be sandwiched between G(n, p(1)) and G(n, p(2)) where p(1) and p(2) are both (1 + o(1))d/n. They proved this conjecture for log n << d >= n(1/3-o(1)), with a defect in the sandwiching: G(n, d) contains G(n, p(1)) perfectly, but is not completely contained in G(n, p(2)). The embedding G(n, p(1)) subset of G(n, d) was improved by Dudek, Frieze, Rucinski and Sileikis to d = o(n). In this paper, we prove Kim-Vu's sandwich conjecture, with perfect containment on both sides, for all d where min {d, n - d} >> n/root log n The sandwich theorem allows translation of many results from G(n, p) to G(n, d) such as Hamiltonicity, the chromatic number, the diameter, etc. It also allows translation of threshold functions of phase transitions from G(n, p) to bond percolation of G(n, d). In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability of small subgraph appearances in a random factor of a pseudorandom graph, which is of independent interest.