Optimal path and cycle decompositions of dense quasirandom graphs

Stefan Glock, Daniela Kühn, Deryk Osthus

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let $0<p<1$…