Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2011.09449 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912374667083776 |
|---|---|
| author | Gao, Pu Isaev, Mikhail McKay, Brendan |
| author_facet | Gao, Pu Isaev, Mikhail McKay, Brendan |
| contents | Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if $d\gg \log n$, then the random $d$-regular graph $G(n,d)$ can be ``sandwiched'' between $G(n,p_*)$ and $G(n,p^*)$ where $p_*$ and $p^*$ are both asymptotically equal to $d/n$.
This famous conjecture was previously proved for all $d\gg (n\log n)^{3/4}$.
In this paper, we confirm the conjecture when $d \gg \log^4 n$. We also extend this result to near-regular degree sequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_09449 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Kim--Vu's sandwich conjecture is true for $d \gg \log^4 n$ Gao, Pu Isaev, Mikhail McKay, Brendan Combinatorics Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if $d\gg \log n$, then the random $d$-regular graph $G(n,d)$ can be ``sandwiched'' between $G(n,p_*)$ and $G(n,p^*)$ where $p_*$ and $p^*$ are both asymptotically equal to $d/n$. This famous conjecture was previously proved for all $d\gg (n\log n)^{3/4}$. In this paper, we confirm the conjecture when $d \gg \log^4 n$. We also extend this result to near-regular degree sequences. |
| title | Kim--Vu's sandwich conjecture is true for $d \gg \log^4 n$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2011.09449 |