Phase Transitions in Combinatorial Structures: Universality of the Three-Parameter Mittag-Leffler Distribution

Abstract

Many combinatorial models involving trees, graphs, tilings, words,random walks, partitions, and permutations are enumerated by compositions of functions. Such composition schemes are ubiquitous in combinatorics, number theory, statistical mechanics, and probability theory.

We provide a unifying explanation for various phenomena observed in the combinatorics and statistical physics literature, focusing on models in which a combinatorial parameter taking the value k is assigned a Gibbs (Boltzmann) weight q^k.

We prove the existence of a phase transition: there is a critical value (q=q_c) at which the limiting distribution of the parameter is a three-parameter Mittag-Leffler distribution, whereas it is Gaussian in the supercritical regime (q>q_c) and follows a Boltzmann distribution in the subcritical regime (0 < q < q_c).

We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, as well as a phenomenon discovered by Krattenthaler concerning wall contacts in watermelons (families of nonintersecting lattice paths).

Our framework also explains why and under what conditions limiting distributions such as the Rayleigh, half-normal, chi, stable, and Airy distributions arise.

No prior knowledge of analytic combinatorics is required for this talk.We will begin with an overview of the subject, including some historical background. The proofs will only be sketched, and full details can be found in the following papers by Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner:

Please click here for participating the talk online.