Titelaufnahme

Titel
Lattice path combinatorics / von Michael Wallner
VerfasserWallner, Michael
Begutachter / BegutachterinDrmota, Michael
Erschienen2013
Umfang91 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2013
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
URNurn:nbn:at:at-ubtuw:1-76129 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Lattice path combinatorics [0.88 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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 (hier Kombinatorik und Komplexe Analysis).

Zusammenfassung (Englisch)

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