Matas Sileikis: Half-sandwich of random graphs

In 2004 Kim and Vu conjectured that if d grows faster than log n as n tends to infinity, then one can “sandwich” a random d-regular graph G(n,d) between two binomial random graphs G(n,p1) and G(n,p2), both of which have asymptotic expected degree d. By “sandwiching” we mean that with high probability G(n,p1) is a subgraph of G(n,d) and G(n,d) is a subgraph of G(n,p2). The motivation for “sandwiching” is to reduce the study of monotone properties (like hamiltonicity) of G(n,d) to the study of the simpler model G(n,p). We present recent progress on the Kim and Vu conjecture and its hypergraph analogue.