Mixing Times of Markov Chains on Degree Constrained Orientations of
Planar Graphs
Authors: Stefan Felsner ; Daniel Heldt
NULL##NULL
Stefan Felsner;Daniel Heldt
We study Markov chains for $\alpha$-orientations of plane graphs, these are
orientations where the outdegree of each vertex is prescribed by the value of a
given function $\alpha$. The set of $\alpha$-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 $\alpha$-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 $\alpha$ and a class of plane
triangulations of constant maximum degree such that the up-down Markov chain on
the $\alpha$-orientations of these graphs is slowly mixing.