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