Longest cycles in sparse random digraphs

DOI10.1002/RSA.20435MaRDI QIDQ2844080zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

Publication date 27 August 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.3147

zbMATH Keywords

directed graphslong cycleslong pathsrandom digraphsparse random graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

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 $cG(n,p)$ with $p=c/n$ has a cycle on at all but at most $(1+epsilon)c{e}^{-c}n$ vertices with high probability, where $epsilon=epsilon(c)o0$ as $coinfty$. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph $cD(n,p)$ 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 $cD(n,p)$ with $p=c/n$ has a cycle containing all but $(2+epsilon)e^{-c}n$ vertices w.h.p., where $epsilon=epsilon(c)o0$ as $coinfty$. 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.

Recommendations

• A scaling limit for the length of the longest cycle in a sparse random digraph
• Packing and counting arbitrary Hamilton cycles in random digraphs
• scientific article; zbMATH DE number 3916307
• Cycle lengths in sparse random graphs
• A note on long cycles in sparse random graphs

Cites work

• An algorithm for finding Hamilton paths and cycles in random graphs
• Clutter percolation and random graphs
• Cycles in a random graph near the critical point
• scientific article; zbMATH DE number 3693325 (Why is no real title available?)
• Long cycles in subgraphs of (pseudo)random directed graphs
• Long paths in sparse random graphs
• On large matchings and cycles in sparse random graphs
• On tail probabilities for martingales
• The longest path in a random graph
• The size Ramsey number of a directed path

Cited in

(14)

• On sparse graphs with dense long paths
• A scaling limit for the length of the longest cycle in a sparse random graph
• Long cycles in subgraphs of (pseudo)random directed graphs
• Approximating the Longest Cycle Problem in Sparse Graphs
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• A classification of isomorphism-invariant random digraphs
• On the method of typical bounded differences
• Cycle lengths in sparse random graphs
• Cycle lengths in randomly perturbed graphs
• A scaling limit for the length of the longest cycle in a sparse random digraph
• The birth of the strong components
• \(d\)-connectivity of the random graph with restricted budget
• Cycle lengths in sparse graphs

This page was built for publication: Longest cycles in sparse random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2844080)