Longest cycles in sparse random digraphs12. Issue 1 (28th May 2012) - Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
Abstract Long paths and cycles in sparse random graphs and digraphs were studied intensively in the 1980's. It was finally shown by Frieze in 1986 that the random graph <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{G}}(n, p)$\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg224zs4pv" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> with p = c/n has a cycle on at all but at most (1 + ε)ce−cn vertices with high probability, where ε = ε (c) → 0 as c → ∞. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n, p)$\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg224zs4n9" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> no tight result was known and the best estimate was a factor of c/2 away from the corresponding lower bound. In this work we close this gap and show that the random digraph <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n, p)$\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg224zs4f0" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> with p = c/n has a cycle containing all but (2 + ε)e−cn vertices w.h.p., where ε = ε (c) → 0 as c → ∞. This is essentially tight since w.h.p. such a random digraph contains (2e−c − o(1))n vertices with zero in‐degree or out‐degree. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013