Exact solutions of lattice walk models
This semester, we will continue our course of analytic combinatorics and focus on exactly solvable model of lattice walk (discrete Random walk) .
The idea of analytic combinatorics is to solve the discrete problems through analyzing of the generating functions. Generating functions can be treated both as algebraic objects (formal series ring) and continuous functions. We may combine the vision of combinatorics and analysis to find the explicit solutions.
The idea of analytic combinatorics is to solve the discrete problems through analyzing of the generating functions. Generating functions can be treated both as algebraic objects (formal series ring) and continuous functions. We may combine the vision of combinatorics and analysis to find the explicit solutions.
Lecturer
Date
3rd March ~ 26th May, 2026
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday,Wednesday | 13:30 - 15:05 | A3-2-303 | ZOOM 08 | 787 662 9899 | BIMSA |
Prerequisite
complex analysis, calculus, undergraduate algebra
Syllabus
1 Review of analytic combinatorics, generating functions, symbolic method
2 Basic analytic combinatorics and the kernel method.
3 solving quarter plane lattice walk via the algebraic kernel method and obstinate kernel method
4 Gessel's walk and polynomial equations with one catalytic variable
5 The Tutte's invariants method
6 Some basic knowledge of covering manifold, Weistrass p-function, Galois theory
7 Random walk in the quarter plane, a geometric insight of the kernel
8 Riemann boundary value problem of Caleman type
9 Counting coloured planar maps, the Potts model
2 Basic analytic combinatorics and the kernel method.
3 solving quarter plane lattice walk via the algebraic kernel method and obstinate kernel method
4 Gessel's walk and polynomial equations with one catalytic variable
5 The Tutte's invariants method
6 Some basic knowledge of covering manifold, Weistrass p-function, Galois theory
7 Random walk in the quarter plane, a geometric insight of the kernel
8 Riemann boundary value problem of Caleman type
9 Counting coloured planar maps, the Potts model
Reference
Flajolet, Philippe, and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.
Bousquet-Mélou, Mireille, and Arnaud Jehanne. "Polynomial equations with one catalytic variable, algebraic series and map enumeration." Journal of Combinatorial Theory, Series B 96.5 (2006): 623-672.
Banderier, Cyril, and Philippe Flajolet. "Basic analytic combinatorics of directed lattice paths." Theoretical Computer Science 281.1-2 (2002): 37-80.
Fayolle, Guy, et al. Random walks in the quarter-plane. Vol. 40. New York: Springer-Verlag, 1999.
Bousquet-Mélou, Mireille, and Marni Mishna. "Walks with small steps in the quarter plane." Algorithmic probability and combinatorics 520 (2010): 1-39.
Bernardi, Olivier, and Mireille Bousquet-Mélou. "Counting colored planar maps: algebraicity results." Journal of Combinatorial Theory, Series B 101.5 (2011): 315-377.
Bernardi, Olivier, and Mireille Bousquet-Mélou. "Counting coloured planar maps: differential equations." Communications in Mathematical Physics 354.1 (2017): 31-84.
Raschel, K. (2012). Counting walks in a quadrant: a unified approach via boundary value problems. Journal of the European Mathematical Society, 14(3), 749-777.
Bousquet-Mélou, Mireille, and Arnaud Jehanne. "Polynomial equations with one catalytic variable, algebraic series and map enumeration." Journal of Combinatorial Theory, Series B 96.5 (2006): 623-672.
Banderier, Cyril, and Philippe Flajolet. "Basic analytic combinatorics of directed lattice paths." Theoretical Computer Science 281.1-2 (2002): 37-80.
Fayolle, Guy, et al. Random walks in the quarter-plane. Vol. 40. New York: Springer-Verlag, 1999.
Bousquet-Mélou, Mireille, and Marni Mishna. "Walks with small steps in the quarter plane." Algorithmic probability and combinatorics 520 (2010): 1-39.
Bernardi, Olivier, and Mireille Bousquet-Mélou. "Counting colored planar maps: algebraicity results." Journal of Combinatorial Theory, Series B 101.5 (2011): 315-377.
Bernardi, Olivier, and Mireille Bousquet-Mélou. "Counting coloured planar maps: differential equations." Communications in Mathematical Physics 354.1 (2017): 31-84.
Raschel, K. (2012). Counting walks in a quadrant: a unified approach via boundary value problems. Journal of the European Mathematical Society, 14(3), 749-777.
Audience
Advanced Undergraduate
, Graduate
, Postdoc
, Researcher
Video Public
Yes
Notes Public
Yes
Language
English