Chain Lengths in Certain Random Directed Graphs

We study the random directed graph with vertex set {1, …, n} in which the directed edges (i, j) occur independently with probability c_n/n for i and probability zero for i ? j. Let M_n (resp., L_n) denote the length of the longest path (resp., longest path starting from vertex 1). When c_n is bounded away from 0 and ∞ as n→∞, the asymptotic behavior of M_n was analyzed in previous work of the author and J. E. Cohen. Here, all restrictions on c_n are eliminated and the asymptotic behavior of L_n is also obtained. In particular, if c_n/ln(n)→∞ while c_n/n→0, then both M_n/c_n and L_n/c_n are shown to converge in probability to the constant e.