文章基本信息

标题：On the Probability That a Random Digraph Is Acyclic
本地全文：下载
作者：Dimbinaina Ralaivaosaona ; Vonjy Rasendrahasina ; Stephan Wagner 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：159
页码：25:1-25:18
DOI：10.4230/LIPIcs.AofA.2020.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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â' â^Z} n^{1/3} â"{D(n,1/n (1+Î¼ n^{-1/3})) is acyclic}.
关键词：Random digraphs; acyclic digraphs; asymptotics