The scaling limit of a critical random directed graph

DOI10.1214/22-AAP1859MaRDI QIDQ6104019zbMATH OpenOpenAlexFDO

Authors Christina Goldschmidt, Robin Stephenson

Publication date 5 June 2023

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.05397

zbMATH Keywords

phase transitionrandom directed graphscaling limit

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We consider the random directed graph $vecG(n,p)$ with vertex set $1,2,ldots,n$ in which each of the $n(n-1)$ possible directed edges is present independently with probability $p$. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at $p=1/n$, with critical window $p=1/n+lambda{n}^{-4/3}$ for $lambdainmathcalR$. We show that, within this critical window, the strongly connected components of $vecG(n,p)$, ranked in decreasing order of size and rescaled by $n^{-1/3}$, converge in distribution to a sequence $(mathcal{C}_1,mathcal{C}_2,ldots)$ of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an $el{l}^1$ sequence metric for which two directed multigraphs are close if there are compatible isomorphisms between their vertex and edge sets which roughly preserve the edge-lengths. Our proofs rely on a depth-first exploration of the graph which enables us to relate the strongly connected components to a particular spanning forest of the undirected ErdH{o}s-R'enyi random graph $G(n,p)$, whose scaling limit is well understood. We show that the limiting sequence $(mathcal{C}_1,mathcal{C}_2,ldots)$ contains only finitely many components which are not loops. If we ignore the edge lengths, any fixed finite sequence of 3-regular strongly connected directed multigraphs occurs with positive probability.

Recommendations

• The continuum limit of critical random graphs
• Giant components in three-parameter random directed graphs
• The strong giant in a random digraph
• The critical window in random digraphs
• Critical random graphs: limiting constructions and distributional properties

Cites work

• A course in metric geometry
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Critical random graphs: limiting constructions and distributional properties
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4078444 (Why is no real title available?)
• scientific article; zbMATH DE number 3711987 (Why is no real title available?)
• scientific article; zbMATH DE number 48952 (Why is no real title available?)
• scientific article; zbMATH DE number 51724 (Why is no real title available?)
• Local limits of Markov branching trees and their volume growth
• Markov Chains
• Path-based depth-first search for strong and biconnected components
• Random trees and applications
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Tessellations of random maps of arbitrary genus
• The continuum limit of critical random graphs
• The critical behavior of random digraphs
• The critical window in random digraphs
• The distribution of the maximum Brownian excursion
• The phase transition in the evolution of random digraphs
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• The transitive closure of a random digraph

Cited in

(7)

• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• Scaling limit for the random walk on the largest connected component of the critical random graph
• The birth of the strong components
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• Continuum limit of critical inhomogeneous random graphs
• Scaling of components in critical long-range geometric random graphs on the 2-dim torus
• Percolation in simple directed random graphs with a given degree distribution

This page was built for publication: The scaling limit of a critical random directed graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6104019)