Half-sandwich of random graphs
Graphs, Hypergraphs, and Computing
13 May 15:30 - 16:30
Matas Sileikis - Uppsala University
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.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU