Counting directed acyclic and elementary digraphs

zbMATH Open1452.05087arXiv2001.08659MaRDI QIDQ2199812FDOQ2199812

Elie de Panafieu, Sergey Dovgal

Publication date: 14 September 2020

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

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.

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

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)

Cites Work

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

Cited In (7)

• The asymptotic number of acyclic digraphs. I
• Topological additive numbering of directed acyclic graphs
• Exact enumeration of satisfiable 2-SAT formulae
• A combinatorial link between labelled graphs and increasingly labelled Schröder trees
• On counting homomorphisms to directed acyclic graphs
• Counting acyclic and strong digraphs by descents
• The birth of the strong components

   Recommendations

• Title not available (Why is that?) 👍 👎
• On a random mapping (T, P_j) 👍 👎
• The critical behavior of random digraphs 👍 👎
• On the largest strong components in \(m\)-out digraphs 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)