Michael Wallner

Multitudinous probabilistic and combinatorial objects are associated with generating functions satisfying a composition scheme F(z)=G(H(z)). The analysis becomes challenging when this scheme is critical (i.e., G and H are simultaneously singular). Motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely F(z,u)=G(uH(z))M(z). We also consider a variant of this scheme, which allows us to analyse the number of H-components of a given size in F. We prove that these two models lead to a rich world of limit laws, where we identify the key role played by a new universal law introduced in this article: the three-parameter Mittag-Leffler distribution, which is essentially the product of a beta and a Mittag-Leffler distribution. We also prove (double) phase transitions, additionally involving Boltzmann and mixed Poisson distributions, bringing a unified explanation of the associated thresholds. In all cases we obtain moment convergence and local limit theorems. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular Pólya urns, and the Chinese restaurant process.

We answer some questions on the asymptotics of ballot walks raised in [S. B. Ekhad and D. Zeilberger, April 2021] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.

A compacted binary tree is a graph created from a binary tree such that repeatedly occurring subtrees in the original tree are represented by pointers to existing ones, and hence every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf. We solve the asymptotic counting problem for this class as well as a closely related, further simplified class. For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed as well as compacted trees of bounded right height and given size, when the size tends to infinity.