Combinatorial and probabilistic aspects of lattice path models

• Main Author: Schwerdtfeger, Uwe
• Format: Doctoral or Postdoctoral Thesis
• Language: English
• Published: Bielefeld University 2010
• Subjects: Gitterpfad; Stochastische Matrix; Abzählende Kombinatorik; Asymptotik; Zufallsmatrix; Kombinatorische Wahrscheinlichkeit; Lattice path; Random matrix; Enumerative combinatorics; Asymptotics; Combinatorial probability; ddc:510; Arctic; Schwerdtfeger
• Online Access: https://nbn-resolving.org/urn:nbn:de:hbz:361-16740; https://pub.uni-bielefeld.de/record/2303814; https://pub.uni-bielefeld.de/download/2303814/2303817

Schwerdtfeger U. Combinatorial and probabilistic aspects of lattice path models . Bielefeld (Germany): Bielefeld University; 2010. Nach einer Einordnung der Ergebnisse in ihre jeweiligen Gebiete im ersten Kapitel beschäftigt sich das zweite Kapitel mit zufälligen Pflasterungen eines Sechsecks mit 60-Grad-Rauten und festen Randbedingungen. Dabei wird die Gleichverteilung auf der Menge der Pflasterungen eines Sechsecks mit Seitenlängen r,s,t angenommen und das Grenzverhalten studiert, wenn r,s und t proportional gegen unendlich streben. Gewisse Statistiken verhalten sich dann wie die Eigenwerte großer Zufallsmatrizen aus dem Gaußschen Unitären Ensemble. Dies ist in der Literatur eingehend besprochen worden. Im Kapitel 2 wird gezeigt, dass diese Verteilungen auch im Unterensemble symmetrischer Pflasterungen auftreten oder, äquivalent dazu, im Ensemble der Pflasterungen des "halbierten" Sechsecks. Dabei fällt auch ein Beweis des "Arctic Circle"-Phänomens für dieses Ensemble ab: Entlang der dem Sechseck eingeschriebenen Ellipse findet ein scharfer Übergang von einem hochgeordneten zu einem ungeordneten Regime statt. Dieses Phänomen ist im genannten Unterensemble bisher nur in einer Arbeit von Forrester und Nordenstam vermutet worden. Das dritte Kapitel beschäftigt sich mit ebenen Partitionen in einer r mal s mal t-Box. Dies sind r mal s-Matrizen mit nichtnegativen ganzen Einträgen kleiner oder gleich t, die entlang der Zeilen und Spalten monoton abfallen. Das Volumen einer ebenen Partition ist die Summe der Einträge. Es wird für r,s,t fest die Gleichverteilung angenommen und gezeigt, dass die zentrierten und normalisierten Volumenzufallsvariablen schwach gegen die Standardnormalverteilung konvergieren, falls von r,s,t zwei Werte gegen unendlich streben. Analoge Ergebnisse gelten auch für Symmetrieunterklassen. Im vierten Kapitel werden Flächengesetze für Symmetrieunterklassen von Treppenpolygonen hergeleitet. Diese bestehen aus zwei gerichteten Pfaden auf dem Quadratgitter mit denselben Start- und Endpunkten, aber ohne gemeinsame Vertizes dazwischen. Es wird die asymptotische Verteilung der Fläche im Limes eines großen Umfangs untersucht, wobei die Gleichverteilung auf allen Polygonen desselben festen Umfangs mit vorgeschriebener Symmetrie angenommen wird. Die Grenzverteilungen sind, abgesehen von einigen trivialen Fällen, die Flächenverteilungen der Brownschen Exkursion und des Brownschen Mäanders. Im fünften Kapitel werden schließlich zwei Klassen von selbstmeidenden Polygonen auf dem Quadratgitter abgezählt, d.h. ihre erzeugenden Funktionen werden ausgerechnet und analysiert. Es handelt sich dabei um "vorausschauende Polygone" (prudent polygons), d.h. beim Durchlaufen der Randkurve von einem ausgezeichneten Startvertex zum Endvertex wird nie ein Schritt in Richtung eines bereits besuchten Vertex gegangen. Für die erzeugende Funktion der allgemeinen Klasse solcher Polygone kann man bis dato nur ein System von Funktionalgleichungen angeben. Erfolgreicher dagegen sind die Untersuchungen zu zwei natürlichen Unterklassen. Diese können vollständig gelöst, d.h. ihre erzeugenden Funktionen explizit angegeben werden. Die erzeugende Funktion der kleineren Klasse ist algebraisch und unter anderem Namen schon aus der Literatur bekannt. Für die erzeugende Funktion der größeren Klasse wird eine Darstellung als unendliche Reihe von algebraischen Funktionen angegeben. Für diese wird gezeigt, dass sie keine lineare Differentialgleichung mit polynomialen Koeffizienten erfüllt. The first chapter is an introduction which puts the subsequent chapters into the respective scientific contexts. After that, the second chapter deals with random tilings of a hexagon with 60-degree unit rhombi with fixed boundary conditions. Every tiling of a hexagon with integer side lengths r,s,t is considered equally probable and the limiting behaviour is studied as r,s and t tend to infinity proportionally. Certain statistics behave like the eigenvalues of a large random matrix of the Gaussian Unitary Ensemble. This is discussed exhaustively in the literature. In Chapter 2 it is shown that these distributions also occur in the sub-ensemble of symmetric tilings or, equivalently, in tilings of the "half-hexagon". As a by-product an "arctic circle phenomenon" is proven: There is a highly ordered and a highly unordered regime with a sharp boundary between the two being the inscribed ellipse. This phenomenon has so far only been conjectured for this sub-ensemble in a paper by Forrester and Nordenstam. The third chapter is on plane partitions fitting inside an r times s times t box. These are r times s matrices with non-negative integer entries less than or equal to t, such that entries are decreasing monotonically along rows and columns. The volume is the sum of the entries. For fixed r,s,t the uniform distribution is considered and it is shown that the centred and normalised volume random variables converge weakly to the the standard normal distribution as two values of r,s and t tend to infinity. Analogous assertions are shown to hold true for symmetry sub-classes. In Chapter 4 area limit laws for symmetry classes of staircase polygons are derived. These consist of two directed paths on the square lattice sharing the same starting and terminal vertex but no vertex in between. We consider the uniform distribution on all polygons of a given fixed perimeter with a prescribed symmetry and study the asymptotic distribution of area in the limit of a large perimeter. In the interesting cases these limiting distributions are the area distributions of the Brownian excursion and the Brownian meander. In Chapter 5 two classes of self-avoiding polygons on the square lattice are enumerated, i.e. their generating functions are computed and analysed. The classes in question are so-called prudent polygons, i.e. the boundary walk starting at a distinguished vertex and ending at a vertex adjacent to this vertex never takes a step towards an already occupied vertex. For the general class of these polygons so far only a system of functional equations is known. In Chapter 5 two sub-classes are solved, i.e. their generating functions are computed explicitly. One class has already occurred in the literature under a different name and has an algebraic generating function. The generating function of the other class is given as an infinite series of algebraic functions. Careful analysis shows that this function cannot satisfy a linear differential equation with polynomial coefficients.