Counting directed acyclic and elementary digraphs

MaRDI QIDQ2199812zbMATH OpenFDO

Authors Sergey Dovgal, Elie de Panafieu

Publication date 14 September 2020

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.08659, http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2020//2.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

strongly connected components of directed acyclic graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Directed acyclic graphs (DAGs) can be characterised as directed graphs whose strongly connected components are isolated vertices. Using this restriction on the strong components, we discover that when $m=cn$, where $m$ is the number of directed edges, $n$ is the number of vertices, and $c<1$, the asymptotic probability that a random digraph is acyclic is an explicit function $p(c)$, such that $p(0)=1$ and $p(1)=0$. When $m=n(1+mu{n}^{-1/3})$, the asymptotic behaviour changes, and the probability that a digraph is acyclic becomes $n^{-1/3}C(mu)$, where $C(mu)$ is an explicit function of $mu$. {L}uczak and Seierstad (2009, Random Structures & Algorithms, 35(3), 271--293) showed that, as $muo-infty$, the strongly connected components of a random digraph with $n$ vertices and $m=n(1+mu{n}^{-1/3})$ directed edges are, with high probability, only isolated vertices and cycles. We call such digraphs elementary digraphs. We express the probability that a random digraph is elementary as a function of $mu$. Those results are obtained using techniques from analytic combinatorics, developed in particular to study random graphs.

Review text

The strongly connected components of directed acyclic graphs (DAGs) are only isolated vertices. Using this fact, the authors discover that when \(m =cn\), where \(m\) is the number of directed edges, \(n\) is the number of vertices, and \(c <1\) is a constant, the asymptotic probability for a random digraph to be acyclic is an explicit function \(p(c) = e^{-c}(1- c)\). When \(m = n(1 + \mu n^{-1/3})\), the asymptotic behavior changes, and the probability for a digraph to be acyclic becomes \(n^{-1/3}C(\mu)\), where \(C(\mu)\) is an explicit function of \(\mu\). \textit{T. Łuczak} and \textit{T. G. Seierstad} [Random Struct. Algorithms 35, No. 3, 271--293 (2009; Zbl 1214.05157)] showed that, as \(\mu \rightarrow -\infty\), the strongly connected components of a random digraph with \(n\) vertices and \(m = n(1 +\mu n^{-1/3})\) directed edges are, with high probability, only isolated vertices and cycles, and such digraphs are called elementary digraphs. The present authors also express the probability for a random digraph to be elementary as a function of \(\mu\). These results are obtained using techniques from analytic combinatorics, developed in particular for the study of random graphs.

Recommendations

• scientific article; zbMATH DE number 7651064
• On a random mapping (T, P_j)
• The critical behavior of random digraphs
• On the largest strong components in m-out digraphs
• scientific article; zbMATH DE number 3997846
• Six Ways of Looking at Burtin's Lemma
• Directed cycles and related structures in random graphs. I: Static properties
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• The critical window in random digraphs

Cites work

• Airy phenomena and analytic combinatorics of connected graphs
• Analytic combinatorics
• Analytic combinatorics of connected graphs
• Asymptotics of bivariate analytic functions with algebraic singularities
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• Counting acyclic digraphs by sources and sinks
• On the Number of Maximal Vertices of a Random Acyclic Digraph
• On the shape of a random acyclic digraph
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• The asymptotic number of acyclic digraphs. I
• The birth of the giant component
• The critical behavior of random digraphs
• The phase transition in the evolution of random digraphs
• Threshold functions for small subgraphs in simple graphs and multigraphs

Cited in

(12)

• The asymptotic number of acyclic digraphs. I
• Counting acyclic and strong digraphs by descents
• Counting strongly-connected, moderately sparse directed graphs
• On the shape of a random acyclic digraph
• On counting homomorphisms to directed acyclic graphs
• Topological additive numbering of directed acyclic graphs
• Counting acyclic orderings in directed acyclic graphs
• A combinatorial link between labelled graphs and increasingly labelled Schröder trees
• The birth of the strong components
• Exact enumeration of satisfiable 2-SAT formulae
• The number of descendants in a random directed acyclic graph
• Asymptotic behaviour of the poles of a special generating function for acyclic digraphs

This page was built for publication: Counting directed acyclic and elementary digraphs

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