1 Search Results for "Rasendrahasina, Vonjy"


Document
On the Probability That a Random Digraph Is Acyclic

Authors: Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


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

Cite as

Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner. On the Probability That a Random Digraph Is Acyclic. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2020.25,
  author =	{Ralaivaosaona, Dimbinaina and Rasendrahasina, Vonjy and Wagner, Stephan},
  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 =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.25},
  URN =		{urn:nbn:de:0030-drops-120557},
  doi =		{10.4230/LIPIcs.AofA.2020.25},
  annote =	{Keywords: Random digraphs, acyclic digraphs, asymptotics}
}
  • Refine by Author
  • 1 Ralaivaosaona, Dimbinaina
  • 1 Rasendrahasina, Vonjy
  • 1 Wagner, Stephan

  • Refine by Classification
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Random graphs

  • Refine by Keyword
  • 1 Random digraphs
  • 1 acyclic digraphs
  • 1 asymptotics

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail