Workshop 2026

A workshop on Pandag-related topics will take place on July 16th and July 17th at TU Wien.

List of participants:

Schedule of the wokshop:

Élie de Panafieu: An analytic link between directed acyclic graphs and pairs of non-oriented graphs

The graphic generating function of directed acyclic graphs (DAGs) can be expressed using the exponential generating function of (non-oriented) graphs. Exploiting graph decomposition, this reduces theenumeration of DAGs to the enumeration of a particular family of pairs of graphs. We deduce the asymptotics of DAGs on n vertices and m edges for m/n below or close to 1/2. Extending this approach beyond 1/2 is an interesting open problem. This is joint work with Sergey Dovgal.

Amaury Curiel : Asymptotic analysis of a particular class of DOAGs

Ordered directed acyclic graphs (DOAGs) arise naturally as data structures for representing objects that share common substructures. In this talk, we focus on two families of DOAGs: the unary-binary and binary variants. We aim to understand how many of them exist as their size grows large, as well as to understand the typical distribution of certain parameters. We first present an asymptotic counting result: the number of binary DOAGs with 𝑛 nodes grows like Θ(𝑛! 4^𝑛 exp( 3 𝑎_1 𝑛^(1/3)) sqrt(n)), where 𝑎_1 is the largest root of the Airy function. This behavior, called a stretched exponential, is obtained via a “guess and check” type method that we will detail. We then turn to the study of parameters for DOAGs of “small right height”. By extending a combinatorial framework arising from the enumeration of relaxed trees, we will obtain functional equations describing our structures, which we will study using methods from analytic combinatorics in order to understand the asymptotic distribution of certain parameters. This is joint work with Antoine Genitrini, Bernhard Gittenberger, Neena Mathew and Michael Wallner.

Nadja Azzouz: Asymptotic analysis of generating functions arising from dynamic graphs

We study generating functions arising from sequentially growing labeled graphs where at each step either a new vertex is created or a new edge between two existing vertices is added. We provide explicit representations of the generating functions and derive asymptotic formulas for their coefficients using Laplace’s method and Bessel function approximations in the undirected model, and Hayman admissibility combined with the saddle point method in the directed model. Finally, we study a natural parameter of each model and indicate further parameter studies. This is joint work with Olivier Bodini, Francis Durand and Bernhard Gittenberger.

Khaydar Nurligareev: Growing binary trees

In this talk, we present a dynamic process for generating binary trees: at each step, active leaves called anchors either stop growing or are replaced by a subtree consisting of two new anchors attached to an internal node. We focus on active trees that retain at least one anchor and continue to grow. As these trees grow infinitely large, we demonstrate that the proportion of trees with a fixed number of anchors stabilizes toward a certain limit. We also show that the number of valid anchor configurations follows a meta-Fibonacci sequence, connect the model to Mandelbrot polynomials, and provide a uniform random generation algorithm for trees of a given profile. Finally, by incorporating tree height into our study, we reveal the geometric limit shapes and boundary forms of possible configurations as both the height and the number of nodes approach infinity.
This is joint work with Olivier Bodini and Antoine Genitrini.

Neena Mathew: On increasing trees with two types of labels

We study a model of leaf-labeled increasing trees where the internal vertices carry labels of another type which are strictly increasing on root-to-leaf paths but globally within the tree label repetitions of the labels can appear. These trees can be generated by a combinatorial evolution process, which yields a functional equation for generating functions that encode the number of trees with a fixed number of leaves. The counting sequence has been studied in a very different context by Babai and Lengyel, but we rederive the result using an approximate Borel transform as heuristic to guess the exponential growth rate. Appropriately rescaling the counting sequence, we obtain a recurrence that can be analyzed by using asymptotic results on Stirling numbers of the second kind. This alternative approach allows the study of parameters of the underlying combinatorial structure. This is joint work with Bernhard Gittenberger.

Oriane Crouzet: Analysis and Optimization of the Alias Method Using Integer Arithmetic

The Alias method is a classical algorithm, developed in the 1970s, for& generating random variables from a discrete probability distribution in constant& time. However, this classical approach has some limitations, like its reliance& on floating-point arithmetic, which may introduce rounding errors. To overcome these limitations, several variants of the Alias method have been proposed. Among them, some aim to approach the optimality of the random sampling method introduced by Knuth and Yao, particularly by reducing the number of random bits required during the sampling process. The objective of this presentation is to study a new version of the Alias method based exclusively on integer arithmetic, and to compare it with the main approaches currently available in the literature. A particular attention will be paid to optimize the number of random bits consumed during the sampling phase and to evaluate the computational performance of this new algorithm. This is joint work with Simon Dreyer, Antoine Genitrini and Mehdi Naima.

Benedikt Stufler: Limit laws of random simplex tree-child networks

We prove that the longer and shorter Sackin indices of a uniformly random simplex tree-child network with $n$ taxa admit joint distributional limits after rescaling by $n^{-7/4}$. The limiting distributions are described by functionals of a Brownian excursion. We also identify the limiting law of the height after rescaling by $n^{-3/4}$, thereby answering a question of Zhang~(2022). Moreover, we establish sharp tail bounds for the height, which imply convergence of all moments in the above distributional limits. We further obtain a scaling limit for the entire height profile of the leaves. Finally, we determine the local limits of large simplex networks around the fixed root, a uniformly random vertex, and a uniformly random leaf. This is joint work with Víctor J. Maciá.

Era Cahyati: The Sackin index of level-2 networks

The Sackin index is an important measure for the balance of phylogenetic trees and has been extended to level-k networks. Recently, Fuchs and Gittenberger computed explicit constants for the mean of the Sackin index of level-1 network (also known as galled trees). In level-2 networks, a biconnected component may contain up to two reticulation nodes. We investigate the Sackin index for leaf-labeled level-2 networks and determine the mean, including the explicit numerical value for the multiplicative factor, which was not known before. The method is based on generating functions and analytic combinatorics. This is joint work with Bernhard Gittenberger.

Antoine Genitrini: Graphs of Shortest Paths

In this talk, we will define a new class of directed acyclic graphs, called Graphs of Shortest Paths. We will sketch their asymptotic enumeration, as well as the key ideas behind the proof. We will see that this class of graphsshares common features with several classical classes. Finally, we will present a method for the uniform generation of these graphs at a fixed size. This is joint work with Mehdi Naima and Simon Dreyer.

Francis Durand: Entropic Generation of Binary Words

Michael Wallner: The decompressed tree size of k-ary chains