[Back]

A. Nessmann:
"Lattice Walks in the Quarter Plane";
Supervisor: M. Drmota; Institut für Diskrete Mathematik und Geometrie, 2020; final examination: 2020-08.

Many combinatorial problems can be reduced to the study of lattice paths. In analytic combinatorics,
one assigns to such paths a generating function, whose properties can then be studied using complex analysis. The results often allow conclusions about the initial combinatorial problem.
The topic of this work are paths with small steps in the quarter plane, in particular the question when the corresponding generating function is holonomic. In 2010, M. Bousquét-Melou and M.
Mishna conjectured that holonomy of the generating function is equivalent to the finiteness of a certain group associated with the set of allowed steps. This leads to a multitude of publications,
and eventually to the proof of the conjecture. The aim of this work is to give an overview ofthe proof, but also to provide an introduction to the surprisingly diverse theory which is used therein.
The first part of this work starts with a short introduction to holonomic functions and lattice paths in general. The kernel equation of the generating function is derived, which is in a sense
the center piece of all that comes later. The kernel method for treating such equations is introduced,
which immediately allows solving the question for walks in the plane and the half plane. Restricting ourselves to walks in the quarter plane, the group of a walk is introduced, and holonomy is proven for all paths with a finite group using orbit summation methods.
In the next part, the main topic of interest are those paths with infinite group. In order to effectively study those, some technical prerequisites are required, in particular a bit of theory about
analytic continuation and Riemann surfaces, and basic information about Algebraic curves, in particular elliptic curves. Using these tools, two proofs for the non-holonomy in the infinite group
case are outlined in the last section. While the underlying idea is always studying the poles of certain functions, the techniques applied are remarkably different. One proof works directly with
meromorphic continuations of the kernel equation and the group on the Riemann surface, the other uses an algebraic approach, utilizing valuation theory on elliptic curves in connection with Galois theory of difference rings.