DROPS

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

Phase Transition for Tree-Rooted Maps

Authors: Marie Albenque, Éric Fusy, and Zéphyr Salvy

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

We introduce a model of tree-rooted planar maps weighted by their number of 2-connected blocks. We study its enumerative properties and prove that it undergoes a phase transition. We give the distribution of the size of the largest 2-connected blocks in the three regimes (subcritical, critical and supercritical) and further establish that the scaling limit is the Brownian Continuum Random Tree in the critical and supercritical regimes, with respective rescalings √{n/log(n)} and √n.

Cite as

Marie Albenque, Éric Fusy, and Zéphyr Salvy. Phase Transition for Tree-Rooted Maps. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albenque_et_al:LIPIcs.AofA.2024.6,
  author =	{Albenque, Marie and Fusy, \'{E}ric and Salvy, Z\'{e}phyr},
  title =	{{Phase Transition for Tree-Rooted Maps}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.6},
  URN =		{urn:nbn:de:0030-drops-204413},
  doi =		{10.4230/LIPIcs.AofA.2024.6},
  annote =	{Keywords: Asymptotic Enumeration, Planar maps, Random trees, Phase transition}
}

Search Results

Documents authored by Salvy, Zéphyr

Asymptotic Transfer in Critical Recursive Composition Schemes

Abstract

Cite as

Phase Transition for Tree-Rooted Maps

Abstract

Cite as

Thanks for your feedback!

Could not send message