Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-13T09:25:29.840Z Has data issue: false hasContentIssue false
  • English
  • Français

The critical window in random digraphs

Part of: Graph theory

Published online by Cambridge University Press:  08 October 2021

Matthew Coulson
Matthew Coulson*
Affiliation:
Department of Mathematics, Universitat Politècnica de Catalunya, Spain.
*
Email: [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the component structure of the random digraph D(n,p) inside the critical window $p = n^{-1} + \lambda n^{-4/3}$ . We show that the largest component $\mathcal{C}_1$ has size of order $n^{1/3}$ in this range. In particular we give explicit bounds on the tail probabilities of $|\mathcal{C}_1|n^{-1/3}$ .

Keywords

Random digraphcritical windowphase transition

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C20: Directed graphs (digraphs), tournaments
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 31 , Issue 3 , May 2022 , pp. 411 - 429
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Addario-Berry, L., Broutin, N. and Goldschmidt, C. (2012) The continuum limit of critical random graphs. Probab. Theory Related Fields 152 367–406.CrossRefGoogle Scholar
Aldous, D. (1997) Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 812–854.Google Scholar
Bollobás, B. (1984) The evolution of random graphs. Trans. Amer. Math. Soc. 286 257–274.CrossRefGoogle Scholar
Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5 17–60.Google Scholar
Goldschmidt, C. and Stephenson, R. (2019) The Scaling Limit of a Critical Random Directed Graph. arXiv preprint arXiv:1905.05397.Google Scholar
Grimmett, G. and Stirzaker, D. (2001) Probability and Random Processes. Oxford University Press.Google Scholar
Janson, S., Knuth, D. E., Łuczak, T. and Pittel, B. (1993) The birth of the giant component. Random Struct. Algor. 4 233–358.CrossRefGoogle Scholar
Janson, S., Łuczak, T. and RuciŃski, A. (2011) Random Graphs, vol. 45. John Wiley & Sons.Google Scholar
Karp, R. M. (1990) The transitive closure of a random digraph. Random Struct. Algor. 1 73–93.CrossRefGoogle Scholar
Łuczak, T. (1990) Component behavior near the critical point of the random graph process. Random Struct. Algor. 1 287–310.CrossRefGoogle Scholar
Łuczak, T. (1990) The phase transition in the evolution of random digraphs. J. Graph Theory 14 217–223.CrossRefGoogle Scholar
Łuczak, T., Pittel, B. and Wierman, J. C. (1994) The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 721–748.CrossRefGoogle Scholar
Łuczak, T. and Seierstad, T. (2009) The critical behavior of random digraphs. Random Struct.& Algor. 35 271–293.CrossRefGoogle Scholar
Martin-Löf, A. (1986) Symmetric sampling procedures, general epidemic processes and their theshold limit theorems. J. Appl. Probab. 23 265–282.CrossRefGoogle Scholar
McDiarmid, C. (1980) Clutter percolation and random graphs. In Combinatorial Optimization II. Springer, pp. 17–25.CrossRefGoogle Scholar
Nachmias, A. and Peres, Y. (2010) The critical random graph, with martingales. Israel J. Math. 176 29–41.CrossRefGoogle Scholar
Palásti, I. (1966) On the strong connectedness of directed random graphs. Studia Sci. Math. Hungar 1 205–214.Google Scholar
Pérez-Giménez, X. and Wormald, N. (2013) Asymptotic enumeration of strongly connected digraphs by vertices and edges. Random Struct. Algor. 43 80–114.CrossRefGoogle Scholar
Pittel, B. (2001) On the largest component of the random graph at a near critical stage. J. Comb. Theory, Ser. B 82 237–269.CrossRefGoogle Scholar
Pittel, B. (2013) Counting strongly-connected, moderately sparse directed graphs. Random Struct.& Algor. 43 49–79.CrossRefGoogle Scholar
Scott, A. D. and Sorkin, G. B. (2006) Solving sparse random instances of max cut and max 2-CSP in linear expected time. Comb. Prob. Comp. 15 281–315.CrossRefGoogle Scholar
Tyurin, I. S. (2010) Refinement of the upper bounds of the constants in Lyapunov’s theorem. Russian Math. Surv. 65 586–588.CrossRefGoogle Scholar
Venkatesh, S. S. (2013) The Theory of Probability: Explorations and Applications. Cambridge University Press.Google Scholar
Wright, E. M. (1977) Formulae for the number of sparsely-edged strong labelled digraphs. The Quarterly Journal of Mathematics 28 363–367.CrossRefGoogle Scholar