3:00pm - 5:00pmSymbolic Combinatorics
Chair(s): Shaoshi Chen (Chinese Academy of Sciences), Manuel Kauers (Johannes Kepler University, Linz, Austria), Stephen Melczer (University of Pennsylvania)
In recent years algorithms and software have been developed that allow researchers to discover and verify combinatorial identities as well as understand analytic and algebraic properties of generating functions. The interaction of combinatorics and symbolic computation has had a beneficial impact on both fields. This minisymposium will feature 12 speakers describing recent research combining these areas.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Diagonals, determinants, and rigidity
Christoph Koutschan
Radon Institute for Computational and Applied Mathematics
Diagonals of rational functions occur naturally in lattice statistical mechanics and enumerative combinatorics. We find that the diagonals of certain families of rational functions can be expressed as pullbacked hypergeometric 2F1 functions. On the other hand, the enumeration of combinatorial objects is often encoded by determinants. We study several families of binomial determinants that count the number of lozenge tilings of hexagonal domains with holes. Also graphs play a prominent role in combinatorics, and we are particularly interested in the aspect of rigidity. Using a novel combinatorial algorithm for computing the number of complex realizations of a maximally rigid graph, we explore exhaustively the Laman numbers of graphs with up to 13 vertices.
Central Limit Theorems from the Location of Roots of Probability Generating Functions
Marcus Michelen
University of Pennsilvania
For a discrete random variable, what information can we deduce from the roots of its probability generating function? We consider a sequence of random variables X_n taking values between 0 and n, and let P_n(z) be its probability generating function. We show that if none of the complex zeros of the polynomials P_n(z) are contained in a neighborhood of 1 in the complex plane then a central limit theorem occurs, provided the variance of X_n isn't subpolynomial in n. This result is sharp a sense that will be made precise, and thus disproves a conjecture of Pemantle and improves upon various results in the literature. This immediately improves a multivariate central limit theorem of Ghosh, Liggett and Pemantle, and has ramifications for certain variables that arise in graph theory contexts. This is based on joint work with Julian Sahasrabudhe.
Periodic Pólya urns and an application to Young tableaux
Michael Wallner
TU Wien
Pólya urns are urns where at each unit of time a ball is drawn uniformly at random and is replaced by some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p.
Our key tool are generating functions, which encode all possible urn compositions after a certain number of steps. The evolution of the urn is then translated into a system of differential equations and we prove that the moment generating functions are D-finite. From these we derive asymptotic forms of the moments. When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions.
Furthermore, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions. This is joint work with Cyril Banderier and Philippe Marchal.
