A scaling limit for the length of the longest cycle in a sparse random digraph. Issue 1 (14th June 2021)

• Record Type: Journal Article
• Authors: Anastos, Michael; Frieze, Alan
• Is Part Of: Random structures & algorithms. Volume 60:Issue 1(2022)
• Page Start: 3
• Page End: 24
• Publication Date: 2021-06-14
• Subjects: longest cycle -- random digraphs -- scaling limit; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21030
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We discuss the length L → c, n of the longest directed cycle in the sparse random digraph D n, p, p = c / n, c constant. We show that for large c there exists a function f → ( c ) such that L → c, n / n → f → ( c ) a.s. The function f → ( c ) = 1 − ∑ k = 1 ∞ p k ( c ) e − k c where p k is a polynomial in c . We are only able to explicitly give the values p 1, p 2, although we could in principle compute any p k .