×

The critical behavior of random digraphs. (English) Zbl 1214.05157

Summary: We study the critical behavior of the random digraph \(D(n,p)\) for \(np = 1 + \epsilon \), where \(\epsilon = \epsilon (n) = o(1)\). We show that if \(\epsilon ^{3}n \to -\infty \), then a.a.s. \(D(n,p)\) consists of components which are either isolated vertices or directed cycles, each of size \(O_p(|\epsilon |^{-1})\). On the other hand, if \(\epsilon ^{3}n \to \infty \), then a.a.s. the structure of \(D(n,p)\) is dominated by the unique complex component of size \((4 + o(1))\epsilon ^{2}n\), whereas all other components are of size \(O_p(\epsilon ^{-1})\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, The evolution of random graphs, Trans Am Math Soc 286 pp 257– (1984) · Zbl 0579.05046
[2] Bollobás, Random graphs pp xviii+498– (2001) · doi:10.1017/CBO9780511814068
[3] Cohen, Giant components in three-parameter random directed graphs, Adv Appl Probab 24 pp 845– (1992) · Zbl 0779.05049
[4] Janson, Cycles and unicyclic components in random graphs, Combin Probab Comput 12 pp 27– (2003) · Zbl 1010.05072
[5] Janson, The birth of the giant component, Random Structures Algorithms 4 pp 231– (1993) · Zbl 0795.05127
[6] Janson, Random graphs pp xii+333– (2000) · doi:10.1002/9781118032718
[7] Karp, The transitive closure of a random digraph, Random Structures Algorithms 1 pp 73– (1990) · Zbl 0712.68076
[8] Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 pp 287– (1990) · Zbl 0745.05048
[9] Łuczak, The phase transition in the evolution of random digraphs, J Graph Theory 14 pp 217– (1990) · Zbl 0712.05051
[10] Łuczak, Cycles in a random graph near the critical point, Random Structures Algorithms 2 pp 421– (1991) · Zbl 0755.05089 · doi:10.1002/rsa.3240020405
[11] Łuczak, Random trees and random graphs, Random Structures Algorithms 13 pp 485– (1998) · Zbl 0959.05111
[12] Luczak, The phase transition in the cluster-scaled model of a random graph, Random Structures Algorithms 28 pp 215– (2006)
[13] Łuczak, The structure of a random graph at the point of the phase transition, Trans Am Math Soc 341 pp 721– (1994) · Zbl 0807.05065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.