License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.13
URN: urn:nbn:de:0030-drops-89069
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8906/
Go to the corresponding LIPIcs Volume Portal

Bodini, Olivier ; Courtiel, Julien ; Dovgal, Sergey ; Hwang, Hsien-Kuei

Asymptotic Distribution of Parameters in Random Maps

pdf-format:
LIPIcs-AofA-2018-13.pdf (0.9 MB)

Abstract

We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.

BibTeX - Entry

@InProceedings{bodini_et_al:LIPIcs:2018:8906,
  author =	{Olivier Bodini and Julien Courtiel and Sergey Dovgal and Hsien-Kuei Hwang},
  title =	{{Asymptotic Distribution of Parameters in Random Maps}},
  booktitle =	{29th International Conference on Probabilistic,  Combinatorial and Asymptotic Methods for the Analysis of Algorithms  (AofA 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8906},
  URN =		{urn:nbn:de:0030-drops-89069},
  doi =		{10.4230/LIPIcs.AofA.2018.13},
  annote =	{Keywords: Random maps, Analytic combinatorics, Rooted Maps, Beta law, Limit laws, Patterns, Generating functions, Riccati equation}
}

Keywords: Random maps, Analytic combinatorics, Rooted Maps, Beta law, Limit laws, Patterns, Generating functions, Riccati equation
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI