The birth of the strong components

DOI10.1002/rsa.21176arXiv2009.12127OpenAlexW3087986783MaRDI QIDQ6119218

Dimbinaina Ralaivaosaona, Elie de Panafieu, Sergey Dovgal, Vonjy Rasendrahasina, Stephan G. Wagner

Publication date: 29 February 2024

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

generating functionsphase transitiondirected acyclic graphsrandom directed graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Directed graphs (digraphs), tournaments (05C20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The leading root of the partial theta function
• Random 2 XORSAT phase transition
• The maximum of Brownian motion with parabolic drift
• Moments of the location of the maximum of Brownian motion with parabolic drift
• Asymptotic behaviour of the poles of a special generating function for acyclic digraphs
• The first cycles in an evolving graph
• The asymptotic number of acyclic digraphs. I
• The asymptotic number of acyclic digraphs. II
• Counting acyclic digraphs by sources and sinks
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Airy phenomena and analytic combinatorics of connected graphs
• Phase transition of random non-uniform hypergraphs
• Counting directed acyclic and elementary digraphs
• Generating functions of some families of directed uniform hypergraphs
• Robust Hamiltonicity of random directed graphs
• The number of strongly connected directed graphs
• Acyclic orientations of graphs
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Random directed graphs are robustly Hamiltonian
• Random Graphs and Complex Networks
• Longest cycles in sparse random digraphs
• Introduction to Random Graphs
• The critical behavior of random digraphs
• Birth of a Strongly Connected Giant in an Inhomogeneous Random Digraph
• The transitive closure of a random digraph
• On the strength of connectedness of a random graph
• The phase transition in the evolution of random digraphs
• Integrals involving Airy functions
• A Recurrence Related to Trees
• FORMULAE FOR THE NUMBER OF SPARSELY-EDGED STRONG LABELLED DIGRAPHS
• Counting strong digraphs
• Hamilton Cycles in Random Regular Digraphs
• Exact and asymptotic solutions to a PDE that arises in time-dependent queues
• Paths in graphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Zeros of generalized Airy functions
• Analytic combinatorics of connected graphs
• The birth of the giant component
• Random Graphs
• The stability of spiral flow between rotating cylinders
• On the existence of a factor of degree one of a connected random graph
• The Number of Strong Digraphs
• On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$
• Structure of the Random Graphs $\mathcal{G}_m (x|h)$
• Über das Spektrum bei Eigenschwingungen ebener Laminarströmungen
• The critical window in random digraphs
• Packing, counting and covering Hamilton cycles in random directed graphs