When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.25
URN: urn:nbn:de:0030-drops-120557
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12055/
 Go to the corresponding LIPIcs Volume Portal

### On the Probability That a Random Digraph Is Acyclic

 pdf-format:

### Abstract

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}.

### BibTeX - Entry

```@InProceedings{ralaivaosaona_et_al:LIPIcs:2020:12055,
author =	{Dimbinaina Ralaivaosaona and Vonjy Rasendrahasina and Stephan Wagner},
title =	{{On the Probability That a Random Digraph Is Acyclic}},
booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages =	{25:1--25:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-147-4},
ISSN =	{1868-8969},
year =	{2020},
volume =	{159},
editor =	{Michael Drmota and Clemens Heuberger},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},