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
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to