2026-07-21T23:51:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12055 2024-03-06T10:49:17Z ddc:004 open_access

On the Probability That a Random Digraph Is Acyclic Ralaivaosaona, Dimbinaina Rasendrahasina, Vonjy Wagner, Stephan Random digraphs acyclic digraphs asymptotics Given a positive integer n and a real number p ∈ [0,1], let D(n,p) denote the random digraph defined in the following way: each of the binom(n,2) possible edges on the vertex set {1,2,3,…,n} is included with probability 2p, where all edges are independent of each other. Thereafter, a direction is chosen independently for each edge, with probability 1/2 for each possible direction. In this paper, we study the probability that a random instance of D(n,p) is acyclic, i.e., that it does not contain a directed cycle. We find precise asymptotic formulas for the probability of a random digraph being acyclic in the sparse regime, i.e., when np = O(1). As an example, for each real number μ, we find an exact analytic expression for φ(μ) = lim_{n→ ∞} n^{1/3} ℙ{D(n,1/n (1+μ n^{-1/3})) is acyclic}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dimbinaina Ralaivaosaona and Vonjy Rasendrahasina and Stephan Wagner 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.25 urn:nbn:de:0030-drops-120557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.25 eng https://creativecommons.org/licenses/by/3.0/legalcode