Abstract
Given a planar triangulation, a 3-orientation is an orientation of the
internal edges so all internal vertices have out-degree three. Each
3-orientation gives rise to a unique edge coloring known as a Schnyder wood
that has proven powerful for various computing and combinatorics applications.
We consider natural Markov chains for sampling uniformly from the set of
3-orientations. First, we study a "triangle-reversing" chain on the space of
3-orientations of a fixed triangulation that reverses the orientation of the
edges around a triangle in each move. It was shown previously that this chain
connects the state space and we show that (i) when restricted to planar
triangulations of maximum degree six, the Markov chain is rapidly mixing, and
(ii) there exists a triangulation with high degree on which this Markov chain
mixes slowly. Next, we consider an "edge-flipping" chain on the larger state
space consisting of 3-orientations of all planar triangulations on a fixed
number of vertices. It was also shown previously that this chain connects the
state space and we prove that the chain is always rapidly mixing. The
triangle-reversing and edge-flipping Markov chains both arise in the context of
sampling other combinatorial structures, such as Eulerian orientations and
triangulations of planar point sets, so our results here may shed light on the
mixing rate of these related chains as well.