Counting directed acyclic and elementary digraphs

MaRDI QIDQ2199812zbMATHFDO

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

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) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) 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.

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)

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

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)