Master 2019/2020

Analytic Combinatorics

Type: Elective course (Mathematical Methods of Modelling and Computer Technologies)

Area of studies: Applied Mathematics and Informatics

Delivered by: School of Applied Mathematics

Where: HSE Tikhonov Moscow Institute of Electronics and Mathematics (MIEM HSE)

When: 1 year, 3 module

Mode of studies: distance learning

Instructors: Evgeny Vybornyi

Master’s programme: Mathematical Methods of Modelling and Computer Technologies

Language: English

ECTS credits: 3

Contact hours: 2

Course Syllabus

Abstract

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the generation function equations.

Learning Objectives

• The objective of this course is to form a foundation of Analytic Combinatorics.

Expected Learning Outcomes

• On completion of the course, the student should know the basic tools of analytic combinatorics such as generating functions

Course Contents

• Combinatorial Structures and OGFs
  The first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructionsare integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.
• Labelled Structures and EGFs
  This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. We define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics
• Combinatorial Parameters and MGFs.
  This lecture describes the process of adding variables to mark parameters and then using the constructions form previous topics and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail
• Complex Analysis, Rational and Meromorphic Asymptotics.
  We introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required.
• Applications of Rational and Meromorphic Asymptotics
  We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
• Singularity Analysis
  This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity, approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term
• Applications of Singularity Analysis
  We see how the Flajolet-Odlyzko approach leads to universal laws covering combinatorial classes built with the set, multiset, and recursive sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in previous topics
• Saddle Point Asymptotics
  We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in previous topics.

Assessment Elements

• Exam
• Assessment obtained on the platform https://www.coursera.org/learn/analytic-combinatorics

Interim Assessment

• Interim assessment (3 module)
  0.5 * Assessment obtained on the platform https://www.coursera.org/learn/analytic-combinatorics + 0.5 * Exam

Bibliography

Recommended Core Bibliography

• Flajolet, Philippe. Analytic combinatorics / Philippe Flajolet, Robert Sedgewick. – Cambridge University Press, 2009

Recommended Additional Bibliography

• Fayolle G, Malyshev V, Iasnogorodski R \\ Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, Applications to Queueing Systems and Analytic Combinatorics \\ Springer \\ https://www.springer.com/us/book/9783319509280