Search Results

Documents authored by Drmota, Michael

Document
DOI: 10.4230/LIPIcs.AofA.2022.7
Universal Properties of Catalytic Variable Equations

Authors: Michael Drmota and Eva-Maria Hainzl

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that under certain positivity assumptions the dominant singularity of the solution function has a universal behavior. We have to distinguish between linear catalytic equations, where a dominating square-root singularity appears, and non-linear catalytic equations, where we - usually - have a singularity of type 3/2.
Cite as

Michael Drmota and Eva-Maria Hainzl. Universal Properties of Catalytic Variable Equations. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2022.7,
  author =	{Drmota, Michael and Hainzl, Eva-Maria},
  title =	{{Universal Properties of Catalytic Variable Equations}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.7},
  URN =		{urn:nbn:de:0030-drops-160930},
  doi =		{10.4230/LIPIcs.AofA.2022.7},
  annote =	{Keywords: catalytic equation, singular expansion, univeral asymptotics}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.AofA.2020
LIPIcs, Volume 159, AofA 2020, Complete Volume

Authors: Michael Drmota and Clemens Heuberger

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

Abstract
LIPIcs, Volume 159, AofA 2020, Complete Volume
Cite as

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. 1-402, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{drmota_et_al:LIPIcs.AofA.2020,
  title =	{{LIPIcs, Volume 159, AofA 2020, Complete Volume}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{1--402},
  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},
  URN =		{urn:nbn:de:0030-drops-120296},
  doi =		{10.4230/LIPIcs.AofA.2020},
  annote =	{Keywords: LIPIcs, Volume 159, AofA 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.AofA.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Michael Drmota and Clemens Heuberger

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

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. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2020.0,
  author =	{Drmota, Michael and Heuberger, Clemens},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{0:i--0:xii},
  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.0},
  URN =		{urn:nbn:de:0030-drops-120309},
  doi =		{10.4230/LIPIcs.AofA.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.10
Cut Vertices in Random Planar Maps

Authors: Michael Drmota, Marc Noy, and Benedikt Stufler

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

Abstract
The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.
Cite as

Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. 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. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2020.10,
  author =	{Drmota, Michael and Noy, Marc and Stufler, Benedikt},
  title =	{{Cut Vertices in Random Planar Maps}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-120403},
  doi =		{10.4230/LIPIcs.AofA.2020.10},
  annote =	{Keywords: random planar maps, cut vertices, generating functions, local graph limits}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.18
Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes

Authors: Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.
Cite as

Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2018.18,
  author =	{Drmota, Michael and Ramos, Lander and Requil\'{e}, Cl\'{e}ment and Ru\'{e}, Juanjo},
  title =	{{Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.18},
  URN =		{urn:nbn:de:0030-drops-89117},
  doi =		{10.4230/LIPIcs.AofA.2018.18},
  annote =	{Keywords: Asymptotic enumeration, central limit laws, subcritical graph classes, maximal independent set, maximal matching}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.19
The Number of Double Triangles in Random Planar Maps

Authors: Michael Drmota and Guan-Ru Yu

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
The purpose of this paper is to provide a central limit theorem for the number of occurrences of double triangles in random planar maps. This is the first result of this kind that goes beyond face counts of given valency. The method is based on generating functions, an involved combinatorial decomposition scheme that leads to a system of catalytic functional equations and an analytic extension of the Quadratic Method to systems of equations.
Cite as

Michael Drmota and Guan-Ru Yu. The Number of Double Triangles in Random Planar Maps. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2018.19,
  author =	{Drmota, Michael and Yu, Guan-Ru},
  title =	{{The Number of Double Triangles in Random Planar Maps}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.19},
  URN =		{urn:nbn:de:0030-drops-89120},
  doi =		{10.4230/LIPIcs.AofA.2018.19},
  annote =	{Keywords: Planar maps, pattern occuence, generating functions, quadratic method, central limit theorem}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact