Counting directed acyclic and elementary digraphs

zbMath1452.05087arXiv2001.08659MaRDI QIDQ2199812

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

zbMATH Keywords

strongly connected components of directed acyclic graphs

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

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

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