Chain Lengths in Certain Random Directed Graphs

Charles M. Newman

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish (US)
Pages (from-to)243-253
Number of pages11
JournalRandom Structures & Algorithms
Issue number3
StatePublished - 1992

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Chain Lengths in Certain Random Directed Graphs'. Together they form a unique fingerprint.

Cite this