Approximate Hamilton Decompositions of Random Graphs

Fiachra Knox, Daniela Kühn, Deryk Osthus

We show that if pn >> log n, the binomial random graph G_{n,p} has an approximate Hamilton decomposition. More precisely, we show that in this range G_{n,p} contains a set of edge-…