Chain Lengths in Certain Random Directed Graphs

Charles M. Newman

doi:10.1002/rsa.3240030304

Chain Lengths in Certain Random Directed Graphs

Charles M. Newman

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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<j 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.

Original language	English (US)
Pages (from-to)	243-253
Number of pages	11
Journal	Random Structures & Algorithms
Volume	3
Issue number	3
DOIs	https://doi.org/10.1002/rsa.3240030304
State	Published - 1992

ASJC Scopus subject areas

Software
Mathematics(all)
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.3240030304

Cite this

@article{16dfddab8f754378a869cc6be19ef482,

title = "Chain Lengths in Certain Random Directed Graphs",

abstract = "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 in (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.",

author = "Newman, {Charles M.}",

year = "1992",

doi = "10.1002/rsa.3240030304",

language = "English (US)",

volume = "3",

pages = "243--253",

journal = "Random Structures & Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "3",

}

TY - JOUR

T1 - Chain Lengths in Certain Random Directed Graphs

AU - Newman, Charles M.

PY - 1992

Y1 - 1992

N2 - 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 in (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.

AB - 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 in (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.

UR - http://www.scopus.com/inward/record.url?scp=84990739017&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990739017&partnerID=8YFLogxK

U2 - 10.1002/rsa.3240030304

DO - 10.1002/rsa.3240030304

M3 - Article

AN - SCOPUS:84990739017

SN - 1042-9832

VL - 3

SP - 243

EP - 253

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

IS - 3

ER -

Chain Lengths in Certain Random Directed Graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this