Longest cycles in sparse random digraphs12. Issue 1 (28th May 2012)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 43:Issue 1(2013)
• Page Start: 1
• Page End: 15
• Publication Date: 2012-05-28
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20435
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>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 <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{G}}(n, p)$\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg224zs4pv" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> with <italic>p</italic> = <italic>c</italic>/<italic>n</italic> has a cycle on at all but at most (1 + ε)<italic>ce</italic><sup>−<italic>c</italic></sup><italic>n</italic> vertices with high probability, where ε = ε (<italic>c</italic>) → 0 as <italic>c</italic> → ∞. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n, p)$\end{document}]]></tex-math><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 <italic>c</italic>/2 away from the corresponding lower bound. In this work we close this gap and show that the random digraph <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n, p)$\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg224zs4f0" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> with <italic>p</italic> = <italic>c</italic>/<italic>n</italic> has a cycle containing all but (2 + ε)<italic>e</italic><sup>−<italic>c</italic></sup><italic>n</italic> vertices w.h.p., where ε = ε (<italic>c</italic>) → 0 as <italic>c</italic> → ∞. This is essentially tight since w.h.p. such a random digraph contains (2<italic>e</italic><sup>−<italic>c</italic></sup> − <italic>o</italic>(1))<italic>n</italic> vertices with zero in‐degree or out‐degree. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>