Detailansicht
Classification of lattice walks in the quarter plane
Valerie Roitner
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Herwig Hauser
DOI
10.25365/thesis.40560
URN
urn:nbn:at:at-ubw:1-16423.91619.677449-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit handelt von Gitterwegen. Gitterwege sind gerichtete Polygonzüge mit ganzzahligen Eckpunkten, wobei nur eine fixe Menge an Schritten zugelassen ist. Bei uns werden dies meist eine Teilmenge der sogenannten einfachen Schritte, die den Himmelsrichtungen N, NO, O, SO, S, SW, W und NW entsprechen, sein. Oft stellt man auch Einschränkungen an das Gebiet, das der Weg nicht verlassen darf, wie etwa die Halbebene, die Viertelebene oder den Keil zwischen einer Diagonale und der x-Achse.
Wir werden uns hier überwiegend auf die algebraischen Eigenschaften der erzeugenden Funktionen eines Gitterwegs konzentrieren. Da diese bei der ganzen Ebene und der Halbebene einfach zu klassifizieren sind, betrachten wir hier meistens Wege mit einfachen Schritten in der Viertelebene, die erst unlängst vollständig klassifiziert wurden. Für viele Schrittmengen arbeitet diese Klassifikation mit einer Korrespondenz zwischen der Schrittmenge und einer Gruppe. Nur bei den so genannten Gessel-Wegen schlägt diese Methode fehl. In den letzten Jahren entstanden allerdings drei unterschiedliche Beweise für die Algebraizität der Gessel-Wege, die wir etwas genauer beleuchten werden.
Zu guter Letzt werde ich auch noch einen Ausblick über Gitterwege mit anderen Schritten oder in anderen Regionen sowie über Gitterwege in drei Dimensionen geben.
Abstract
(Englisch)
This master-thesis is about lattice walks. Lattice walks are directed polygonal chains with integer edges, where only a fixed set of steps is allowed. In our case this will be mostly a subset of the so called simple steps, which correspond to the directions N, NE, E, SE, S, SW, W and NW. Often we also impose some conditions on the region which the walk is not allowed to leave, for example the half-plane, the quarter-plane or a wedge between a diagonal and the x-axis.
We will focus mostly on the algebraic properties of the generating function of a walk. Since they are rather simple for walks in the plane and halfplane, we will consider walks with small steps in the quarter plane, which have recently been classified completly. For most step sets this classification works with a correspondence between the step set and a group. Only for the so called Gessel walks this method fails. In recent years three different proofs for the algebraicity of the Gessel walks came up. We will have a closer look at these proofs.
Finally I will also give an overwiev over lattice walks with other step sets or in other regions as well as lattice walks in three dimensions.
Schlagwörter
Schlagwörter
(Englisch)
lattice walks enumerative combinatorics power series
Schlagwörter
(Deutsch)
Gitterwege abzählende Kombinatorik Potenzreihen
Autor*innen
Valerie Roitner
Haupttitel (Englisch)
Classification of lattice walks in the quarter plane
Paralleltitel (Deutsch)
Klassifikation von Gitterwegen in der Viertelebene
Publikationsjahr
2015
Umfangsangabe
71 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Herwig Hauser
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC12699448
Utheses ID
35921
Studienkennzahl
UA | 066 | 821 | |