Search Results

Documents authored by Drmota, Michael

Document
DOI: 10.4230/LIPIcs.AofA.2026.6
Local Central Limit Theorems for Subgraph Counts in Subcritical Graph Families

Authors: Michael Drmota and Yitian Wang

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
It was already established in [Drmota et al., 2017] that subgraph counts in vertex labelled subcritial graph families satisfy a central limit theorem. This result is now sharpened to local central limit theorems. Furthermore this result is generalized to unlabelled subcritical graph families and to multivariate central limit theorems for the joint distribution of finitely many subgraph counts.
Cite as

Michael Drmota and Yitian Wang. Local Central Limit Theorems for Subgraph Counts in Subcritical Graph Families. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2026.6,
  author =	{Drmota, Michael and Wang, Yitian},
  title =	{{Local Central Limit Theorems for Subgraph Counts in Subcritical Graph Families}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.6},
  URN =		{urn:nbn:de:0030-drops-262779},
  doi =		{10.4230/LIPIcs.AofA.2026.6},
  annote =	{Keywords: Subcritical graph classes, subgraph counts, generating functions, functional equations}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.12
Asymptotic Transfer in Critical Recursive Composition Schemes

Authors: Michael Drmota and Zéphyr Salvy

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
The composition ℱ∘𝒢 of two combinatorial classes ℱ and 𝒢 is a standard combinatorial construction and translates into the composition F(G(z)) of their corresponding counting generating functions. Such a composition is called critical if G(ρ_G) = ρ_F, where ρ_F and ρ_G denote the corresponding radii of convergence of F and G, respectively. In this case, both the singular behaviours of F and G influence that of F∘G. Such critical composition schemes arise frequently in map enumeration. For example, by using the block-decomposition, one has M(z) = B (z(1+M(z))²) and ρ_B = ρ_M (1+M(ρ_M))², where M(z) denotes the generating function of all rooted planar maps and B(y) the generating functions of 2-connected rooted planar maps. This can be extended to multivariate generating functions by taking several statistics into account, for example face counts. Since critical composition schemes exhibit (usually) a condensation phenomenon - in the above situation this means that there is a giant 2-connected block of linear size and linearly many small blocks - it is very plausible that statistical properties on 2-connected maps transfer to corresponding properties of all maps and back. The purpose of the present paper is to make this precise at the level of the singular structure of the corresponding multivariate generating functions. In particular, we show that moving 3/2-singularities transfer. Since such singularities are closely related to central limit theorems of the corresponding statistics, this method also provides a kind of transfer of central limit theorems. Actually, this method is quite flexible and is applied to a variety of face and pattern counting statistics in map enumeration.
Cite as

Michael Drmota and Zéphyr Salvy. Asymptotic Transfer in Critical Recursive Composition Schemes. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2026.12,
  author =	{Drmota, Michael and Salvy, Z\'{e}phyr},
  title =	{{Asymptotic Transfer in Critical Recursive Composition Schemes}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.12},
  URN =		{urn:nbn:de:0030-drops-262834},
  doi =		{10.4230/LIPIcs.AofA.2026.12},
  annote =	{Keywords: Analytic Combinatorics, Central Limit Theorem, Pattern Counts, Random Planar Maps, Singularity Analysis}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.17
Singularly Perturbed Discrete Differential Equations and Pattern Counts in Simple Triangulations

Authors: Michael Drmota and Eva-Maria Hainzl

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
Discrete differential equations of order k are of the form R(z,u,F(z,u),Δ F(z,u),…,Δ^kF(z,u)) = 0, where Δ F(z,u) = (F(z,u)-F(z,0))/u and Δ^k F(z,u) = Δ(Δ^{k-1} F(z,u)) for k ≥ 2. Such equations appear most prominently in planar map enumeration but also in several other contexts such as statistical mechanics, lattice path enumeration, pattern avoiding permutations or stack-sortable permutations. Mostly, one is interested in the function F(z,0) that is usually the corresponding counting generating function. In this work, we consider discrete differential equations with an additional parameter x, where the order of the equation is 1 for x = 1 but k > 1 for x ≠ 1. We call such equations singularly perturbed. The solution theory of higher order discrete differential equations is much more involved than for degree 1 and it is a priori not clear that there is a smooth transition from x = 1 to x ≠ 1. The main contribution of this work is to show that there is actually a smooth transition under certain natural assumptions. As an application of this result we consider pattern counts in triangular planar maps and derive a central limit theorem for these counts.
Cite as

Michael Drmota and Eva-Maria Hainzl. Singularly Perturbed Discrete Differential Equations and Pattern Counts in Simple Triangulations. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2026.17,
  author =	{Drmota, Michael and Hainzl, Eva-Maria},
  title =	{{Singularly Perturbed Discrete Differential Equations and Pattern Counts in Simple Triangulations}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.17},
  URN =		{urn:nbn:de:0030-drops-262880},
  doi =		{10.4230/LIPIcs.AofA.2026.17},
  annote =	{Keywords: Discrete differential equations, catalytic equations, generating functions}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact