47 Search Results for "Panagiotou, Konstantinos"

Volume

LIPIcs, Volume 381

37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

AofA 2026, Munich, Germany, June 22-26, 2026

Editors: Konstantinos Panagiotou

Document
Complete Volume
DOI: 10.4230/LIPIcs.AofA.2026
LIPIcs, Volume 381, AofA 2026, Complete Volume

Authors: Konstantinos Panagiotou

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

Abstract
LIPIcs, Volume 381, AofA 2026, Complete Volume
Cite as

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

Copy BibTex To Clipboard

@Proceedings{panagiotou:LIPIcs.AofA.2026,
  title =	{{LIPIcs, Volume 381, AofA 2026, Complete Volume}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{1--520},
  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},
  URN =		{urn:nbn:de:0030-drops-270170},
  doi =		{10.4230/LIPIcs.AofA.2026},
  annote =	{Keywords: LIPIcs, Volume 381, AofA 2026, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.AofA.2026.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Konstantinos Panagiotou

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

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

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

Copy BibTex To Clipboard

@InProceedings{panagiotou:LIPIcs.AofA.2026.0,
  author =	{Panagiotou, Konstantinos},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{0:i--0:xiv},
  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.0},
  URN =		{urn:nbn:de:0030-drops-270164},
  doi =		{10.4230/LIPIcs.AofA.2026.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Flajolet Lecture
DOI: 10.4230/LIPIcs.AofA.2026.1
Laplace, Cauchy and Early Analytic Combinatorics: Chance, Integrals, and Asymptotics (Flajolet Lecture)

Authors: Hsien-Kuei Hwang

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

Abstract
This paper traces early historical developments of analytic combinatorics through a single object: the finite difference Δ^k 0ⁿ (the ordered Stirling numbers). We examine how Laplace transformed this discrete quantity into real integral representations to derive saddle-point approximations, establishing an early encoding-integration-approximation pipeline. Cauchy’s 1815 memoir then moved the same problem toward complex-analytic territory. Through this narrative we illustrate a pivotal transition: from an eighteenth-century algebra of formal identities to a nineteenth-century discipline of ε-δ inequalities.
Cite as

Hsien-Kuei Hwang. Laplace, Cauchy and Early Analytic Combinatorics: Chance, Integrals, and Asymptotics (Flajolet Lecture). 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. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hwang:LIPIcs.AofA.2026.1,
  author =	{Hwang, Hsien-Kuei},
  title =	{{Laplace, Cauchy and Early Analytic Combinatorics: Chance, Integrals, and Asymptotics}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{1:1--1: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.1},
  URN =		{urn:nbn:de:0030-drops-262726},
  doi =		{10.4230/LIPIcs.AofA.2026.1},
  annote =	{Keywords: Laplace, Cauchy, analytic combinatorics, finite differences, saddle-point method, asymptotic analysis, integral transforms, occupancy problem}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.2
Path Length and External Path Length in Random Trees

Authors: Jacob Lundblad and Stephan Wagner

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

Abstract
We consider two closely related concepts in rooted trees: the path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex. For Bienaymé-Galton-Watson trees, the difference is bounded in probability. For three varieties of increasing trees (recursive trees, d-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the difference converges to a constant in probability.
Cite as

Jacob Lundblad and Stephan Wagner. Path Length and External Path Length in Random Trees. 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. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lundblad_et_al:LIPIcs.AofA.2026.2,
  author =	{Lundblad, Jacob and Wagner, Stephan},
  title =	{{Path Length and External Path Length in Random Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{2:1--2:20},
  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.2},
  URN =		{urn:nbn:de:0030-drops-262733},
  doi =		{10.4230/LIPIcs.AofA.2026.2},
  annote =	{Keywords: Path length, external path length, Bienaym\'{e}-Galton-Watson trees, increasing trees}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.3
Efficient Sampling of Increasing Trees

Authors: Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger

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

Abstract
We present a new exact-size sampler for increasing trees that outputs a tree of size n uniformly at random while avoiding the global coefficient pre-computation required by the classical recursive method of Flajolet et al. [Philippe Flajolet et al., 1994]. The key idea is a hybrid oracle-driven rejection scheme in which local sampling decisions are made using interval bounds on the coefficients, with a fallback to exact recurrence computation only on rare ambiguous events. In the bit-complexity model this yields an expected running time of O(nlog n) and it consumes a number of random bits within O(n) of the Shannon entropy, which is information-theoretically optimal up to lower-order terms. The sampler proceeds in two phases. We first generate the unlabeled rooted ordered shape by recursively sampling node arities and subtree sizes and then draw a uniform permutation of {1,…,n} and apply a deterministic increasing-labeling procedure.
Cite as

Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger. Efficient Sampling of Increasing Trees. 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. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azzouz_et_al:LIPIcs.AofA.2026.3,
  author =	{Azzouz, Nadja and Bodini, Olivier and Durand, Francis and Gittenberger, Bernhard},
  title =	{{Efficient Sampling of Increasing Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-262740},
  doi =		{10.4230/LIPIcs.AofA.2026.3},
  annote =	{Keywords: sampling algorithms, bit-complexity, increasing trees, generating functions}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.4
Scaling Limits of Multitype Bienaymé Trees

Authors: Louigi Addario-Berry, Philipp Beltran, Benedikt Stufler, and Paul Thévenin

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

Abstract
We first consider irreducible critical multitype Bienaymé trees and extend the results to the case, when they possess a critical irreducible component with attached subcritical components. We study these trees under two distinct conditioning frameworks: first, conditioning on the value of a linear combination of the numbers of vertices of given types; and second, conditioning on the precise number of vertices belonging to a selected subset of types. We prove that, under a finite exponential moment condition, the scaling limit as the tree size tends to infinity is given by the Brownian Continuum Random Tree. Additionally, we establish strong non-asymptotic tail bounds for the height of such trees. Our main tools include a flattening operation applied to multitype trees and sharp estimates regarding the structure of monotype trees with a given sequence of degrees.
Cite as

Louigi Addario-Berry, Philipp Beltran, Benedikt Stufler, and Paul Thévenin. Scaling Limits of Multitype Bienaymé Trees. 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. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{addarioberry_et_al:LIPIcs.AofA.2026.4,
  author =	{Addario-Berry, Louigi and Beltran, Philipp and Stufler, Benedikt and Th\'{e}venin, Paul},
  title =	{{Scaling Limits of Multitype Bienaym\'{e} Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{4:1--4:16},
  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.4},
  URN =		{urn:nbn:de:0030-drops-262750},
  doi =		{10.4230/LIPIcs.AofA.2026.4},
  annote =	{Keywords: branching processes, multitype trees, scaling limit}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.5
Semi-Simplex Phylogenetic Networks: Tree-Child Networks and Galled Trees

Authors: Michael Fuchs and Tsan-Cheng Yu

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

Abstract
Understanding the size of phylogenetic network classes and the typical shape of a random network from a fixed class has been one of the major research focuses in phylogenetics over the last couple of years. In this extended abstract, we consider two subclasses of the (recently introduced) class of semi-simplex phylogenetic networks, namely, semi-simplex tree-child networks and semi-simplex galled trees. We clarify their sizes relative to the (known) sizes of general tree-child networks and galled trees, respectively, and prove limit laws for parameters of random networks from these classes. Additional classes of semi-simplex networks will be considered in the journal version of this paper.
Cite as

Michael Fuchs and Tsan-Cheng Yu. Semi-Simplex Phylogenetic Networks: Tree-Child Networks and Galled Trees. 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. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.AofA.2026.5,
  author =	{Fuchs, Michael and Yu, Tsan-Cheng},
  title =	{{Semi-Simplex Phylogenetic Networks: Tree-Child Networks and Galled Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{5:1--5: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.5},
  URN =		{urn:nbn:de:0030-drops-262768},
  doi =		{10.4230/LIPIcs.AofA.2026.5},
  annote =	{Keywords: Semi-simplex networks, tree-child networks, galled trees, enumeration, limit laws, Sackin index}
}
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.7
Ancestries and Descendants in a Random DAG

Authors: Fabian Burghart

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

Abstract
We consider a random recursive DAG G_n on the vertex set [n] where every vertex i ≥ 2 has out-degree d, with the targets chosen uniformly at random among the earlier i-1 vertices. For this model, we propose a novel way to investigate the descendants of n (which have recently been studied in a paper by Janson) through what we call ancestry processes. The ancestor process a_i(n) of a vertex i is defined as the number of ancestors of i in G_n, and is closely related to the evolutions of multi-draw Pólya urns. Results on the descendants can then be obtained via asymptotic results on functionals of the ancestry processes, generally leading to technical integral expressions. We employ this method to make progress on two open problems posed by Janson, as well as to provide an alternative proof of a first-moment result contained in his work. We further prove limit theorems for the ancestor processes a_i(n) depending on i.
Cite as

Fabian Burghart. Ancestries and Descendants in a Random DAG. 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. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{burghart:LIPIcs.AofA.2026.7,
  author =	{Burghart, Fabian},
  title =	{{Ancestries and Descendants in a Random DAG}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-262785},
  doi =		{10.4230/LIPIcs.AofA.2026.7},
  annote =	{Keywords: Random DAG, descendants, Markov process, Urn model, Limit theorems}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.8
Local Limit of Random Regular Bipartite Planar Maps

Authors: Nicolas Tokka

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

Abstract
We prove the existence of the local limit of uniform random d-regular bipartite planar maps, for every d ≥ 3, as the number of vertices tends to infinity. The proof relies on a bijection between maps and so-called blossoming trees established in a previous work. After proving local convergence of the associated decorated trees, we extend the bijection to infinite trees and transfer the convergence to planar maps. The limiting object is almost surely one-ended and recurrent for the simple random walk.
Cite as

Nicolas Tokka. Local Limit of Random Regular Bipartite Planar Maps. 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. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tokka:LIPIcs.AofA.2026.8,
  author =	{Tokka, Nicolas},
  title =	{{Local Limit of Random Regular Bipartite Planar Maps}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-262791},
  doi =		{10.4230/LIPIcs.AofA.2026.8},
  annote =	{Keywords: Planar maps, random maps and trees, local convergence}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.9
Link Between Bipartite and General Unicellular Toroidal Maps via Slit-Slide-Sew Bijections

Authors: Jérémie Bettinelli and Dimitri Korkotashvili

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

Abstract
We relate general maps to bipartite maps through a bijection of type slit-slide-sew. We provide an involution on arbitrary genus maps with even degree faces. This enables a full interpretation of the relation between general and bipartite maps, in the case of genus 1 maps with a unique face. The main tool is the use of rotations along well-chosen specific loops. Once a noncontractible simple loop is given, one slits along it, slides one notch, and sews back. This mildly modifies the structure of the map along the loop, changing the parity of the length of other loops crossing it. In the unicellular toroidal setting, the structure of noncontractible loops is simple enough to enable a full correspondence between general and bipartite maps.
Cite as

Jérémie Bettinelli and Dimitri Korkotashvili. Link Between Bipartite and General Unicellular Toroidal Maps via Slit-Slide-Sew Bijections. 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. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bettinelli_et_al:LIPIcs.AofA.2026.9,
  author =	{Bettinelli, J\'{e}r\'{e}mie and Korkotashvili, Dimitri},
  title =	{{Link Between Bipartite and General Unicellular Toroidal Maps via Slit-Slide-Sew Bijections}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-262804},
  doi =		{10.4230/LIPIcs.AofA.2026.9},
  annote =	{Keywords: combinatorial map, enumeration, bijection, unicellular map, slit-slide-sew}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.10
Gibbs Partitions and Lattice Paths

Authors: Niccolò Bosio, Markus Kuba, and Benedikt Stufler

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

Abstract
We study a Gibbs partition model (composition scheme) under a new condition on the component weights, leading to a previously unobserved regime for the number of components. We establish a condensation phenomenon producing a unique giant component, and prove a Cox process limit describing a sublinear power-law growth of sizes of non-maximal components. Our results are motivated by applications to lattice paths and random walks, including simple random walks in the cube, Delannoy paths, pairs of Dyck bridges, urn models and card guessing games.
Cite as

Niccolò Bosio, Markus Kuba, and Benedikt Stufler. Gibbs Partitions and Lattice Paths. 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. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bosio_et_al:LIPIcs.AofA.2026.10,
  author =	{Bosio, Niccol\`{o} and Kuba, Markus and Stufler, Benedikt},
  title =	{{Gibbs Partitions and Lattice Paths}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{10:1--10:12},
  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.10},
  URN =		{urn:nbn:de:0030-drops-262814},
  doi =		{10.4230/LIPIcs.AofA.2026.10},
  annote =	{Keywords: Gibbs partitions, composition schemes, lattice paths, random walks, condensation}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.11
Poisson-Dirichlet Graphons and Permutons

Authors: Benedikt Stufler

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

Abstract
We introduce classes of supergraphs and superpermutations with novel universal graphon and permuton limiting objects whose construction involves the two-parameter Poisson-Dirichlet process introduced by Pitman and Yor (1997). We demonstrate the universality of these limiting objects through general invariance principles in a heavy-tailed regime and establish a comprehensive phase diagram for the asymptotic shape of superstructures.
Cite as

Benedikt Stufler. Poisson-Dirichlet Graphons and Permutons. 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. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{stufler:LIPIcs.AofA.2026.11,
  author =	{Stufler, Benedikt},
  title =	{{Poisson-Dirichlet Graphons and Permutons}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{11:1--11:16},
  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.11},
  URN =		{urn:nbn:de:0030-drops-262821},
  doi =		{10.4230/LIPIcs.AofA.2026.11},
  annote =	{Keywords: Graphons, Permutons, Poisson-Dirichlet point processes}
}
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}
}
  • Refine by Type
  • 46 Document/PDF
  • 8 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 35 2026
  • 7 2025
  • 1 2024
  • 1 2021
  • 2 2019
  • Show More...

  • Refine by Author
  • 7 Panagiotou, Konstantinos
  • 3 Drmota, Michael
  • 3 Stufler, Benedikt
  • 3 Wagner, Stephan
  • 2 Azzouz, Nadja
  • Show More...

  • Refine by Series/Journal
  • 46 LIPIcs

  • Refine by Classification
  • 16 Mathematics of computing → Generating functions
  • 10 Mathematics of computing → Enumeration
  • 8 Mathematics of computing → Combinatorics
  • 7 Mathematics of computing → Discrete mathematics
  • 7 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 6 generating functions
  • 3 analytic combinatorics
  • 2 enumeration
  • 2 increasing trees
  • 2 phase transitions
  • Show More...

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