Lattice path combinatorics

Abstract

Diese Diplomarbeit befasst sich mit drei großen Gebieten der Gitterpunktpfadtheorie: Gerichteten Gitterpunktpfaden mit Fokus auf Anwendungen der "Kernel Method" auf dem Euklidischen Gitter, Pfaden begrenzt auf den ersten Quadranten mit Fokus auf Modelle mit "kleinen Schritten" ebenfalls auf dem Euklidischen Gitter und selbstvermeidenden Pfaden wobei die Herleitung des exakten Wertes der Gitterkonstante ("connective constant") auf dem hexagonalen Gitter präsentiert wird. Im Zentrum des Interesses liegt die Natur der Erzeugenden Funktionen (EF), im Konkreten wird die Frage behandelt, ob diese rational, algebraisch oder holonomisch sind. Die eingeführten Definitionen und die abgeleitete Theorie werden in einheitlicher Weise dargestellt, um eine verständliche und vollständige, aber dennoch tiefgehende und angewandte Einführung in obige Theorie zu geben. Gerichtete Gitterpunktpfade stellen eine gut verstandene Klasse dar, deren EF stets algebraisch sind. Dieses Resultat wird auf Pfade verallgemeinert, welche nur auf der oberen Halbebene agieren und es wird gezeigt, wie die "Kernel Method" verwendet werden kann, um ähnliche Resultate aus einem anderen, aber verwandten Blickwinkel der linearen Rekursionen abzuleiten. Die nächste natürliche Verallgemeinerung stellt die Einschränkung auf den ersten Quadranten dar, was in einer vielfältigeren Theorie der betreffenden EF resultiert. Für die Klasse von Pfaden mit "kleinen Schritten" wird eine Verbindung zwischen EF und der Gruppe des Pfades gezeigt, wodurch ein allgemeines Ergebnis abgeleitet werden kann. Vor 50 Jahren wurde die Hypothese aufgestellt, dass die Gitterkonstante des hexagonalen Gitters gleich $\sqrt{2 + \sqrt{2}}$ ist. Die erst vor kurzem präsentierte Lösung stellt ein ansprechendes Beispiel für den Erfolg von interdisziplinärem Austausch dar (hier Kombinatorik und Komplexe Analysis).

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 $\sqrt{2 + \sqrt{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).