Sandwiching random regular graphs between binomial random graphs

Pu Gao, Mikhail Isaev, Brendan D. McKay

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

Abstract

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n, then the random dregular graph G(n, d) can asymptotically almost surely be “sandwiched” between G(n, p1) and G(n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n ≪ d 6 n1/3−o(1), with a defect in the sandwiching: G(n, d) contains G(n, p1) perfectly, but is not completely contained in G(n, p2). Recently, the embedding G(n, p1) ⊆ G(n, d) was improved by Dudek, Frieze, Ruci´ nski and Šileikis to d = o(n). In this paper, we prove Kim-Vu's sandwich conjecture, with perfect containment on both sides, for all d ≫ n/√log n. For d = O(n/√log n), we prove a weaker version of the sandwich conjecture with p2 approximately equal to (d/n) log n, without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.

Original languageEnglish
Title of host publicationProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
EditorsShuchi Chawla
PublisherSociety for Industrial & Applied Mathematics (SIAM)
Pages690-701
Number of pages12
ISBN (Electronic)9781611975994
DOIs
Publication statusPublished - 2020
EventACM/SIAM Symposium on Discrete Algorithms 2020 - Salt Lake City, United States of America
Duration: 5 Jan 20208 Jan 2020
Conference number: 31st
https://www.siam.org/conferences/cm/conference/soda20

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

ConferenceACM/SIAM Symposium on Discrete Algorithms 2020
Abbreviated titleSODA 2020
CountryUnited States of America
CitySalt Lake City
Period5/01/208/01/20
Internet address

Cite this

Gao, P., Isaev, M., & McKay, B. D. (2020). Sandwiching random regular graphs between binomial random graphs. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (pp. 690-701). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January). Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975994.42