Combinatorics Seminar: Walks, Groups and Difference Equations

Seminar | October 15 | 12-1 p.m. | 939 Evans Hall

 Michael Singer, MSRI

 Department of Mathematics

Many questions in combinatorics, probability and statistical mechanics can be reduced to counting lattice paths (walks) in regions of the plane. A standard approach to counting problems is to consider properties of the associated generating function. These functions have long been well understood for walks in the full plane and in a half plane. Recently much attention has focused on walks in the first quadrant of the plane and has now resulted in a complete characterization of those walks whose generating functions are algebraic, holonomic (solutions of linear differential equations) or at least differentially algebraic (solutions of algebraic differential equations). I will give an introduction to this topic, discuss previous work of Bousquet-Melou, Kauers, Mishna, and others and then present recent work by Dreyfus, Hardouin, Roques and myself applying the theory of QRT maps and Galois theory of difference equations to determine which generating functions satisfy differential equations and which do not.