A Gentle Introduction to Analytic Combinatorics in Several Variables
Lecturer: Prof. Marni Mishna
lecture no.: 326.020
ECTS: 1.50, hours: 1.0
Schedule:
Mon, 21.1., 14:30 - 16:00
Wed, 23.1., 10:15 - 11:45
Thu, 24.1., 15:30 - 17:00
Mon, 28.1., 14:30 - 16:00
Wed, 30.1., 10:15 - 11:45
Thu, 31.1., 15:30 - 17:00
All lectures take place in the RICAM seminar room S2 416-1.
Abstract: Complex analytic techniques have slowly become standard in the combinatorial enumeration toolbox. In particular, singularity analysis of univariate functions can be used to determine asymptotic counting formulas for a huge number of classes. Techniques to handle the multivariate case are necessarily more subtle and challenging. This course will provide the necessary background to understand the basic techniques of coefficient asymptotics of rational functions. We will review univariate techniques, and then examine the methods presented in the 2013 book Analytic Combinatorics in Several Variables (or ACSV) of Pemantle and Wilson, and apply them to pedagogical, yet generalizable examples. We draw our examples from recent research in lattice path enumeration and integer points in polytopes.
Description: The analytic combinatorics framework denotes the systematic study of combinatorial classes using complex analysis to study counting sequences of classes. It proceeds in three major steps: a combinatorial description of the class; a translation to functional equations for the counting generating series; a study of the singularities of soltuions in order to deduce asymptotic enumeration formulas. In this course we will initiate ourselves on the univariate case, which serves as an analogy for more complex examples. Our introductory approach to the multvariate case is focused on the combinatorial case, as we illustrate the process via two families of examples: lattice walks, and vector partitions.
Courses
| # | Topic |
| 1 | Combinatorial Classes and univariate asymptotics |
| 2 | Multivariate series and diagonals |
| 3 | Critical points |
| 4 | Sub-exponential growth |
| 5 | Case study: Lattice paths |
| 6 | Case study: Polytope point enumerators |
References
- Analytic Combinatorics Flajolet and Sedgewick, 2009
- Analytic Combinatorics in several variables Pemantle and Wilson, 2013
- Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions Pemantle and Wilson, 2008.
- PhD Thesis: Melczer 2017
- Walks with small steps in the quarter plane Bousquet-Melou and Mishna, 2010.
- Computing the cotinuous discretely: Integer-point Enumeration in Polyhedra Matthias Beck and Sinai Robins, 2015.