Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5182
Main Title: On the mixing time of the face flip– and up/down Markov chain for some families of graphs
Translated Title: Über die Mischzeit der Face-Flip- und up/down Markov Kette einiger Familien von Graphen
Author(s): Heldt, Daniel
Advisor(s): Felsner, Stefan
Referee(s): Felsner, Stefan
Rote, Günter
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: This dissertation studies two natural Markov chains, each living on a family of finite distributive lattices and some related results on the enumeration of lattice paths. In the first part of this body of work, we introduce a coupling method – the block coupling technique – and apply it to the k-heights of some families of plane graphs. This gives some insight into the behaviour of the up/down Markov chain on these distributive lattices. Espe- cially it yields some upper bounds to the mixing time of the face flip Markov chain for the sets of 2-heights on some families of graphs, which is bounded by a polynomial in the number of vertices of the graph (and therefor polynomial logarithmic in the size of the state space / set of 2-heights). The second part is accepted for publication by the Journal of Integer Sequences. It focuses on the enumeration of bounded lattice paths and uses transfer matrices and methods from linear algebra to do so. Using these techniques we were able to enumerate a rather general class of lattice paths, which reduce to a lot of different well known integer sequences as special cases, and therefore group them together. Also this method looks promising to enumerate other families of sequences, as it links various fields (Graph Theory, Linear Algebra, and Lattice Path Enumeration) in an easily applicable way. Finally, the third part, considers the distributive lattices of α-orientations on planar graphs and the face flip Markov chain on these sets. It uses tower moves, another coupling method, to show that the the up/down Markov chain is rapid mixing on the set of 2-orientations of planar quadrangulations of maximum degree 4. In addition, this part contains results using the congestion of some carefully chosen families of graphs to prove, that for graphs containing vertices with high degree the Markov chain is not rapid mixing, i.e. that the mixing time can not be bound from above by some polynomial in the logarithm of the size of the state space.
Diese Dissertation untersucht zwei natürliche Markov Ketten, die jeweils auf einer Familie endlicher distributiver Verbände leben. Weiterhin enthält sie einige Verwandte Resultate über das Zählen von Gitter-Pfaden. Im ersten Teil der Arbeit stellen wir die Block Coupling Methode vor und wenden sie auf k-heights einiger Familien planarer Graphen an. Dieses gibt etwas Einblick in das Verhalten der up/down-Markov Kette auf diesen distributiven Verbänden. Insbesondere liefern die Untersuchungen einige obere Schranken für die Mischzeit der FaceFlip Markov Kette auf der Menge der 2-heights einiger Graphen-Familien. Wir zeigen dass diese beschränkt ist durch ein Polynom in den Anzahl der Knoten der Graphen (was implizit bedeutet, dass sie polynomiel logarithmisch ist in der Anzahl der 2-heights). Der zweite Teil der Arbeit beschäftigt sich mit dem Zählen beschränkter Gitter-Pfade. Hier werden Transfer Matrizen und Methoden der Linearen Algebra angewendet um diese Pfade zu zählen. Auf diese Art war es möglich, viele bereits bekannte Integer-Sequenzes über die untersuchten beschränkten Gitter-Pfade zu beschreiben und sie daher in einen Zusammenhang zu stellen. Insbesondere scheint diese Methode eine Möglichkeit darzustellen, weitere Familien von Folgen zu untersuchen und sie verbindet einige verschiedene Gebiete der Mathematik. Die Ergebnisse die in diesem Kapitel vorgestellt werden wurden auch vom Journal of Integer Sequences zur Publikation akzeptiert. Der dritte Teil schliesslich beschäftigt sich mit den distributiven Verbänden von Alpha-Orientierungen planarer Graphen und der Face Flip Markov Kette auf diesen. Es werden Tower Movers, eine weitere coupling Methode, genutzt um zu zeigen, dass die up/down Markov Kette für 2-Orientierungen planarer Quadrangulierungen mit maximal Grad 4 schnell mischend ist. Zusätzlich enthält dieser Teil Resultate, die mithilfe sorgfältig konstruierter Graphenfamilien zeigen, dass für Graphen mit hohem Grad nicht erwartet werden kann, dass die untersuchte Markov Kette schnell mischt.
URI: http://depositonce.tu-berlin.de/handle/11303/5553
http://dx.doi.org/10.14279/depositonce-5182
Exam Date: 18-Jun-2015
Issue Date: 2016
Date Available: 16-Jun-2016
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
Subject(s): Markov chains
distributive lattice
lattice paths
Markov Ketten
distributiver Verband
Gitter-Pfade
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
heldt_daniel.pdf1.08 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.