Long paths and Hamiltonicity in random graphs
arXiv:1507.00205
Abstract
We discuss several classical results about long paths and Hamilton cycles in random graphs and present accessible versions of their proofs, relying on the Depth First Search (DFS) algorithm and the notion of boosters.
Based on lecture notes for the mini-course "Long paths and Hamiltonicity in random graphs", delivered by the author at the LMS-EPSRC Summer School on Random Graphs, Geometry and Asymptotic Structure, University of Birmingham, UK, in the summer of 2013