Lattice Path Combinatorics

Diploma Thesis. — Vienna: Vienna University of Technology, 2014. — 100 p. This thesis focuses on three big topics of lattice path theory: Directed lattice paths with focus on applications of the kernel method on the Euclidean lattice, walks confined to the quarter plane with focus on the model of small steps also on the Euclidean lattice and self-avoiding walks where the derivation of the exact value of the connective constant on the hexagonal lattice is presented. The nature of the generating functions (GFs) lies in the center of interest, namely the question concerning its rational, algebraic or holonomic (D-finite) character. The used definitions and the derived theory is put under a unified framework with the goal of giving a coherent and thorough but still deep and applied introduction to the theory of lattice paths. Directed lattice paths possess a well understood structure, as their GF is always algebraic. This result is generalized to walks confined to the half-plane and it is shown how the kernel method can be used to derive similar results from the different view point of linear recurrence relations. The next natural generalization is the restriction to the quarter plane, where the nature of GFs gets much more complicated. For the class of walks with small steps a connection between the GF and the group of the walk is shown and a general result is derived. Fifty years ago the conjecture has been raised that the value of the connective constant on the hexagonal lattice equals √(2 + √2). The problem has been solved only recently and the given solution is an attractive example of the efficiency of interdisciplinary exchange (here combinatorics and complex analysis).