ProV Logo
0
Mixing Times of Markov Chains on Degree ...
Felsner, Stefan...

Free

Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs by Felsner, Stefan ( Author )
Lemonjar Open Access
N.A
09-02-2016
We study Markov chains for α-orientations of plane graphs, these are orientations where the outdegree of each vertex is prescribed by the value of a given function α. The set of α-orientations of a plane graph has a natural distributive lattice structure. The moves of the up-down Markov chain on this distributive lattice corresponds to reversals of directed facial cycles in the α-orientation. We have a positive and several negative results regarding the mixing time of such Markov chains. A 2-orientation of a plane quadrangulation is an orientation where every inner vertex has outdegree 2. We show that there is a class of plane quadrangulations such that the up-down Markov chain on the 2-orientations of these quadrangulations is slowly mixing. On the other hand the chain is rapidly mixing on 2-orientations of quadrangulations with maximum degree at most 4. Regarding examples for slow mixing we also revisit the case of 3-orientations of triangulations which has been studied before by Miracle et al.. Our examples for slow mixing are simpler and have a smaller maximum degree, Finally we present the first example of a function α and a class of plane triangulations of constant maximum degree such that the up-down Markov chain on the α-orientations of these graphs is slowly mixing.
-
Article
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1602.02941
Share this eBook