Printer Friendly

Mixing times of Markov chains on degree constrained orientations of planar graphs.

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 a-orientations of these graphs is slowly mixing.

Keywords: Markov chain, rapidly mixing, torpidly mixing, a-orientations, quadrangulations.

1 Introduction

Let G = (V, E) be a graph and let [alpha] : V [right arrow] [??] be a function, an [alpha]-orientation of G is an orientation with outdeg(v) = [alpha](v) for all vertices v [member of] V .A variety of interesting combinatorial structures on planar graphs can be modeled as [alpha]-orientations. Examples are spanning trees, Eulerian orientations, Schnyder woods of triangulations, separating decompositions of quadrangulations. These and further examples are discussed in [Fel04b] and [FZ08]. In this paper we are interested in Markov chains to sample uniformly from the [alpha]-orientations of a given planar graph G for a fixed [alpha].

A uniform sampler may be used to get data for a statistical approach to typical properties of [alpha]-orientations. Under certain conditions such a chain can be used for approximate counting of [alpha]-orientations. Counting [alpha]-orientations is #P-complete in general. Mihail and Winkler [MW96] have shown that counting Eulerian orientations is #P-complete. Creed [Cre09] has shown that this counting problem remains #P-complete on planar graphs. Further examples of #P-complete variants of counting [alpha]-orientations are given in [FZ08]. In [FZ08, Section 6.2] it is shown that counting [alpha]-orientations can be reduced to counting perfect matchings of a related bipartite graph. The latter problem can be approximately solved using the celebrated algorithm of Jerrum, Sinclair and Vigoda [JSV04] or its improved version by Bezakova et al. [BSVV08]. These algorithms build on random sampling.

For sampling [alpha]-orientations of plane graphs, however, there is a more natural Markov chain. The reversal of the orientation of a directed cycle in an [alpha]-orientation yields another [alpha]-orientation. If G is a plane graph and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are [alpha]-orientations of G, then we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whenever [??] is obtained by reverting a clockwise cycle of [??]. In [Fel04b] it has been shown that this order relation makes the set of [alpha]-orientations of G into a distributive lattice.

A finite distributive lattice is the lattice of down-sets (also known as ideals) of some poset P. Let a 'step' consist in adding/removing a random element of P to/from the down-set. These step yield the updown Markov chain on the distributive lattice. A nice feature of the up-down Markov chain is that it is monotone, see [Pro97]. A monotone Markov chain is suited for using coupling from the past, see [PW96]. This method allows to sample exactly from the uniform distribution on the elements of a distributive lattice.

The challenge in applications of the up-down Markov chain is to analyze its mixing time. In [Pro97] some examples of distributive lattices are described where this chain is rapidly mixing but there are examples where the mixing is slow. Miracle, Randall, Streib and Tetali [MRST16] have investigated the mixing time of the up-down Markov chain for 3-orientations, a class of [alpha]-orientations intimately related to Schnyder woods. They show that there is a class of plane triangulations such that the up-down Markov chain on the 3-orientations of these triangulations is slowly mixing. For positive they show that the chain is rapidly mixing on 3-orientations of plane triangulations with maximum degree at most 6.

In this paper we present similar results for the up-down Markov chain on the 2-orientations of plane quadrangulations. These special 2-orientations are of interest because they are related to separating decompositions, a structure with many applications in floor-planning and graph drawing. For literature on the subject we refer to [dFOdMOl, FHKO10, FFNO11] and references given there. Specifically 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, here we have somewhat simpler examples, compared to those from [MRST16]. Our examples also have a smaller maximum degree, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] instead of O(n) on graphs with n vertices. We also exhibit a function [alpha] and a class of plane graphs of maximum degree 6 such that the up-down Markov chain on the [alpha]-orientations of these graphs is slowly mixing.

2 Preliminaries

In the first part of this section we give some background on the up-down Markov chain on general [alpha]-orientations. Then we discuss 2-orientations and the associated separating decompositions. Finally we provide some background on mixing times for Markov chains.

2.1 The up-down Markov chain of [alpha]-orientations

Let G be a plane graph and [alpha] : V [right arrow] [??] be such that G admits [alpha]-orientations. For [alpha]-orientations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of G we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whenever [??] is obtained by reverting a simple clockwise cycle of [??]. This order relation makes the set of [alpha]-orientations of G into a distributive lattice, see [Fel04b] or [FK09].

The steps of the up-down Markov chain on a distributive lattice [??] = (X, <) correspond to changes x[left and right arrow] x' for covering pairs x [??] x', i.e., pairs x < x' such that there is no y [member of] X with x < y < x'. In other words the up-down Markov chain performs a random walk on the diagram of the lattice. The transition probabilities are (usually) chosen uniformly with a nonzero probability for staying in a state. Since the diagram of a lattice is connected the chain is ergodic. It is also symmetric, hence, the unique stationary distribution is the uniform distribution on the set of [alpha]-orientations.

The steps of the up-down Markov chain of [alpha]-orientations are given by certain reversals of cycles. For a clean description we need the notion of a rigid edge. An edge of G = (V, E) is [alpha]-rigid if it has the same direction in every [alpha]-orientation of G. Let R [??] E be the set of [alpha]-rigid edges. Since directed cycles of an [alpha]-orientation G can be reversed, rigid edges never belong to directed cycles. Define r (v) as the number of rigid edges that have v as a tail and let [alpha]'(v) = [alpha](v) - r(v). Now [alpha]-orientations of G and [alpha]'-orientation of G' = ( V, E - R) are in bijection. And with the inherited plane embedding of G' the distributive lattices are isomorphic.

If G' is disconnected then we can shift connected components of G' to get a plane drawing G# without nested components. Since the orientation, clockwise or counterclockwise, of a directed cycle in G' and G# is identical the distributive lattices of [alpha]'-orientations are isomorphic. The steps of the up-down Markov chain of [alpha]'-orientations of G# are easy to describe, they correspond to the reversal of cycles that form the boundary of bounded faces, the face boundaries of G# are the essential cycles for the up-down Markov chain of [alpha]-orientations of G. In slight abuse of notation we also refer to the up-down Markov chain of [alpha]-orientations of G as the face flip Markov chain, after all the essential cycles of G are faces in G#.

A more algebraic description of the lattice for a disconnected G is as follows: Let H be a component of G, then [[??].sub.[alpha]](G) can be obtained as the product of lattices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[alpha].sub.1] and [[alpha].sub.2] are the restrictions of [alpha] to the vertex sets of G - H and H respectively.

From the previous description it follows that the elements of the poset [P.sub.[alpha]] whose down-sets correspond to elements of [[??].sub.[alpha]](G), i.e., to [alpha]-orientations of G, are essential cycles. It is important to keep the following in mind:

Fact A. An essential cycle can correspond to several elements of the poset [P.sub.[alpha]].

This fact is best illustrated with an example. Figure 1(left) shows the octahedron graph [G.sub.oct] with an Eulerian orientation, this is an a orientation with [alpha](v) = 2 for all v. The orientation is the minimal one in the lattice, it has no counterclockwise oriented cycle. Figure 1(middle) depicts the poset [P.sub.[alpha]] the labels of the elements of [P.sub.[alpha]] refer to the corresponding faces of [G.sub.oct]. The elements 1,1', 1'' all correspond to the same face of [G.sub.oct], this face has to be reversed three times in a sequence of face flips that transforms the minimal Eulerian orientation into the maximal.

The elements of [P.sub.[alpha]] can be found as follows. Let [[??].sub.min] be the minimal [alpha]-orientation, i.e., the one without counterclockwise cycles. Starting from [[??].sub.min] perform flips, i.e., reversals of essential cycles from clockwise to counterclockwise, in any order until no further flip is possible. The unique [alpha]-orientation that admits no flip is the maximal one. The flips of a maximal flip-sequence S are the elements of [P.sub.[alpha]]. Let [??](f) be the number of times an essential cycle f has been flipped in S. Hence, the elements of [P.sub.[alpha]] are {(f, i) : f essential cycle, 1 [less than or equal to] i [less than or equal to] [??](f)}.

[FIGURE 1 OMITTED]

If essential cycles f and f ' share an edge e then from observing the orientation of e we find that between any two appearances of f in a flip-sequence there is a appearance of f '. From this we obtain

Fact B. If essential cycles f and f ' share an edge, then |[??](f) - [??](f')| [less than or equal to] 1.

The above discussion is based on [Fel04b] where [alpha]-orientations of G have been analyzed via [alpha]-potentials, an encoding of down-sets of [P.sub.[alpha]]. If [??] is an [alpha]-orientation, then we say that an essential cycle f is at potential level i in [??] if (f, i) belongs to the down-set [??] of [P.sub.[alpha]] corresponding to [??] but [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.2 2-orientations and separating decompositions

A quadrangulation is a plane graphs whose faces are uniformly of degree 4. Equivalently quadrangulations are maximal bipartite plane graphs.

Let Q be a quadrangulation, we call the color classes of the bipartition white and black and name the two black vertices on the outer face s and t. A 2-orientation of Q is an orientation of the edges such that outdeg(v) = 2 for all v [not equal to] s, t. Since a quadrangulation with n vertices has 2n - 4 edges it follows that s and t are sinks.

A separating decomposition of Q is an orientation and coloring of the edges of Q with colors red and blue such that two conditions hold:

(1) All edges incident to s are ingoing red and all edges incident to t are ingoing blue.

(2) Every vertex v [not equal to] s, t is incident to a nonempty interval of red edges and a nonempty interval of blue edges. If v is white, then, in clockwise order, the first edge in the interval of a color is outgoing and all the other edges of the interval are incoming. If v is black, the outgoing edge is the last one of its color in clockwise order (see Figure 2).

Separating decompositions have been studied in [BH12], [dFOdMOl], [FFNO11], and [FHKO10]. Relevant to us are the following two facts:

Fact 1. In a separating decomposition every vertex v [not equal to] s, t has a unique directed red path v [right arrow] s and a unique blue path v [right arrow] t. The two paths only intersect at v.

[FIGURE 2 OMITTED]

Fact 2. The forget function that associates a 2-orientation with a separating decomposition is a bijection between the set of 2-orientations and the set of separating decompositions of a quadrangulation.

A proof of these facts can be found in [dFOdM01].

2.3 Markov chains and mixing times

We refer to [LPW09] for basics on Markov chains. In applications of Markov chains to sampling and approximate counting it is critical to determine how quickly a Markov chain M converges to its stationary distribution [pi]. Let [M.sup.t] (x, y) be the probability that the chain started in x has moved to y in t steps. The total variation distance at time t is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], here The mixing time of M is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The state space [ohm] of the Markov chains considered by us consists of sets of graphs on n vertices. Such a chain is rapidly mixing if [[tau].sub.mix] is upper bounded by a polynomial of n.

A key tool for lower bounding the mixing time of an ergodic Markov chain is the conductance defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].M([s.sub.1],[s.sub.2]) The connection with [[tau].sub.mix] is given by

Fact T. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This is Theorem 7.3 from [LPW09]. A similar result was already shown in [SJ89]. We will use this inequality mainly in the context of hour glass shaped state spaces where we have a partition [[ohm].sup.-], [[ohm].sup.0], [[ohm].sup.+] of the state space with the property that all paths of the transition graph of the Markov chain that connect [[ohm].sup.-] and [[ohm].sup.+] contain a vertex from [[ohm].sup.0]. The following lemma shows that if [[ohm].sup.-] and [[ohm].sup.+] are large and [[ohm].sup.0] is small with respect to [pi], then the conductance is small.

Lemma 1 If [[ohm].sup.-], [[ohm].sup.0], [[ohm].sup.+] is a partition of [ohm] such that M([s.sub.1], [s.sub.2]) = 0 for all [s.sub.1] [member of] [[ohm].sup.-] and [s.sub.2] [member of] [[ohm].sup.+], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. We assume that [pi]([[ohm].sup.-]) [less than or equal to] [pi]([[ohm].sup.+]) and hence [pi]([[ohm].sup.-]) [less than or equal to] 1/2. Now

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3 Markov chains for 2-Orientations

In this section we study the Markov chain [M.sub.2] for 2-orientations of plane quadrangulations. This is a special instance of the up-down Markov chain for [alpha]-orientations. A step of the chain consists in the reversal of a directed essential cycle.

Lemma 2 The essential cycles for the Markov chain [M.sub.2] of a plane quadrangulation are the four-cycles that contain no rigid edge.

Proof. Let C be a four cycle with nonempty interior. We claim that all the edges incident to a vertex of C and a vertex from the interior of C are rigid. Let U be the set of vertices interior to C and E[U] be the set of edges incident to a vertex of U. Since the cycle together with U induces a quadrangulation we have |E[U] [union] [E.sub.C]| = 2|U [union] C| - 4, i.e., |E[U]| = 2|U|. Hence all edges connecting U to C are out-edges of U, this is the claim.

It follows that every four cycle that contains no rigid edge is a face boundary of a component of the non-rigid edges. This shows that such four-cycles are essential.

Now let C be a cycle of length more than 4 which is a directed cycle in some 2-orientation [??]. A simple counting argument as above shows that in [??] there is an edge [??] oriented from C into the interior. From the correspondence between 2-orientations and separating decompositions together with Fact 1 we know that there is a directed path p starting with [??] and again hitting C. The path p together with a section of the directed cycle C is a directed cycle of [??]. Hence, the edges of p are not rigid and C is not a boundary of a face of a component of the non-rigid edges.

The Markov chain [M.sub.2] can now be readily described. In each step it chooses a four-cycle C and p [member of] [0,1] uniformly at random. If C is directed in the current orientation [??] and p [less than or equal to] 1/2, then C is reversed, otherwise the new state equals the old one. The stationary distribution of M2 is the uniform distribution. (The role of p and the threshold 1/2 is only to ensure that the Markov chain is aperiodic.)

Fehrenbach and Ruschendorf [FR04] have shown that [M.sub.2] is rapidly mixing for certain subsets of the quadrangular grid. In Subsection 3.2 we generalize this result and prove rapid mixing for quadrangulations of maximum degree [less than or equal to] 4.

First, however, we show an exponential lower bound for the mixing time of [M.sub.2] on a certain family of

quadrangulations.

3.1 Slow mixing for 2-orientations

Theorem 1 Let [Q.sub.n] be the quadrangulation on 5n + 1 vertices shown in Figure 3. The Markov chain [M.sub.2] on 2-orientations of [Q.sub.n] has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 3 OMITTED]

Proof. Let [ohm] be the set of 2-orientations of [Q.sub.n]. We define a hour glass partition [[ohm].sub.L], [[ohm].sub.c], [[ohm].sub.R] of this set. The edge ([x.sub.0], s) is rigid, the second out-edge ([x.sub.0], a) of [x.sub.0] is called left if a [member of] {[v.sub.2],..., [v.sub.n]}, it is right if a [member of] {[w.sub.2],. . ., [w.sub.n]} and it is central if a = [x.sub.1]. Now [[ohm].sub.L], [[ohm].sub.c], [[ohm].sub.R] are the sets 2-orientations where the second out-edge of x0 is left, central, and right respectively. With the next claim we show that this is a hour glass partition.

Claim 1. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a step of [M.sub.2] which changes the second out-edge [??] of [x.sub.0], then the step corresponds to the reversal of an essential four-cycle containing [??]. Any four-cycle of [Q.sub.n] that contains [x.sub.0] either only contains edges from [x.sub.0] to vertices from {[x.sub.1], [v.sub.2],..., [v.sub.n]} or it only contains edges from [x.sub.0] to vertices from {[x.sub.1], [w.sub.2],..., [w.sub.n]}. Hence, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Claim 2. |[[OHM].sub.C]| = 1 and Figure 3 shows the unique 2-orientation in this set.

Consider [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. All the edges between {[v.sub.n], [x.sub.n], [w.sub.n]} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are oriented upward in [??], they are rigid. Suppose all the edges between {[v.sub.k], [x.sub.k], [w.sub.k]} and [v.sub.n] are oriented upward in [??]. We also know the directed edges ([v.sub.k], [x.sub.0]) and ([w.sub.k], [x.sub.0]) in [??]. Together this accounts for all out-edges of [v.sub.k], [x.sub.k], and [w.sub.k]. Hence all the edges between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and {[v.sub.k], [x.sub.k], [w.sub.k]} are oriented upward in [??]. These edges cover all the out-edges of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whence all edges between {[v.sub.k-1],[x.sub.k-1],[w.sub.k-1]} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are oriented upward in [??]. With downward induction on k this shows that [??] has to be the 2-orientation shown in Figure 3. A

Claim 3. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From the symmetry of [Q.sub.n] we easily get that |[[OHM].sub.L]| = |[[OHM].sub.R]|. Now let [P.sub.k] be the set of directed path from [x.sub.0] to [v.sub.k] in [??] from Figure 3. If p [member of] [P.sub.k] then ([v.sub.k], [x.sub.0]) together with p forms a directed cycle in [??]. Reverting this cycle yields a 2-orientation that contains the edge ([x.sub.0], [v.sub.k]). This 2-orientation belongs to [[ohm].sub.L]. Different paths in [P.sub.k] yield different orientations. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (in fact equality holds).

It remains to evaluate |[P.sub.k] |. With induction we easily obtain that in [??] there are exactly [3.sup.I-1] directed paths from [x.sub.0] to either of [??] and [??]. Hence |[P.sub.k]| = [3.sup.k-2] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The three claims together with Lemma 1 yield [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Which implies the theorem via Fact T.

3.2 The tower chain for low degree quadrangulations

Following ideas originating from [LRS95] we define a tower Markov chain [M.sub.2T] that extends [M.sub.2]. A single step of [M.sub.2T] can combine several steps of [M.sub.2]. Using a coupling argument we show that [M.sub.2T] is rapidly mixing on quadrangulations of degree at most 4. With the comparison technique this positive result will then be extended to [M.sub.2].

The basic approach for our analysis of [M.sub.2T] on low degree quadrangulations is similar to what Fehrenbach and Ruschendorf [FR04] did on a class of subgraphs of the quadrangular grid. In the context of 3-orientations of triangulations similar methods were applied by Creed [Cre09] to certain subgraphs of the triangular grid and later by Miracle et al. [MRST16] to general triangulations. As Creed [Cre09] noted there is an inaccurate claim in the proof of [FR04]. Later Miracle et al. [MRST12] stepped into the same trap (it has been corrected in the final version [MRST16]). In 3.2.1 below we discuss these issues and show how to repair the proofs.

Let Q be a quadrangulation on n vertices and [ohm] be the set of 2-orientations of Q. From the considerations in Subsection 2.1 we know that there is a redrawing Q# of the subgraph of non-rigid edges of Q such that the essential cycles of Q are the boundaries of bounded faces of Q#. From Lemma 2 we know that these faces are four-faces.

Let [??] be a 2-orientation and C be a simple cycle. With [e.sup.+](C) we denote the number of clockwise edges of C and with [e.sup.-](C) the number of counterclockwise edges. If f is a four-cycle and v(f) = |[e.sup.+](f) - [e.sup.-](f)|, then v(f) can take the values 0, 2, and 4. The face f is oriented if v(f) = 4, it is scrambled if v(f) = 0, and it is blocked is v( f) = 2. If f is blocked, then three edges have the same orientation and one edge does not. We call this the blocking edge of f.

A tower of length k is a sequence ([f.sub.1],[f.sub.2], . . . , [f.sub.k]) of four-cycles of [??] such that each [f.sub.i] for i = 1,.., k - 1 is blocked and [f.sub.k] is oriented. Moreover, in [f.sub.i] the blocking edge of [f.sub.i-1] is opposite to the blocking edge of [f.sub.i] for i = 1,.., k - 1. A tower of length 1 is just an oriented face, Figure 4 shows a tower of length 5.

[FIGURE 4 OMITTED]

Lemma 3 below implies that that removing all blocking edges from a tower T of length k we obtain a connected region whose boundary [delta]T is an oriented cycle with 2k + 2 edges. This is the boundary cycle of the tower. The boundary cycle need not be simple but each edge of [delta]T only belongs to a single face [f.sub.i] [member of] T. Therefore, we can also obtain the effect of reverting [delta]T by reverting [f.sub.k-1],..., [f.sub.1] in this order.

For the following arguments we assume that Q has no nested four-cycles. This is justified by the isomorphism between the lattices of 2-orientations of Q and of [alpha]'-orientations of Q#.

Lemma 3 If [f.sub.i] and [f.sub.j] are different faces of a tower T and they share an edge, then j [member of] {i - 1, i + 1} and the shared edge is the blocking edge ofone ofthem.

Proof. The construction sequence [f.sub.1]. . . , [f.sub.k]; of a tower T =([f.sub.1] . . . , [f.sub.k]) yields a directed walk in the dual. The edges of this walk are the duals of the blocking edges. Each f has at most one blocking edge and [f.sub.k] has no blocking edge. Hence, there is no repetition of faces in a tower. It follows that [delta]T is an oriented cycle. Two faces [f.sub.i] [NOT EQUAL TO] [f.sub.j] do not share an edge e of [delta]T. This is because they would be the faces of the two sides of e whence e would be clockwise in one of them and counterclockwise in the other, however, [delta]T is uniformly oriented.

Lemma 4 If f is a four-cycle, then there is at most one tower starting with f = [f.sub.1].

Proof. Again we look at the construction sequence of a tower and the corresponding directed path in the dual. Each [f.sub.i] has at most one blocking edge, hence, there is a unique candidate for [f.sub.i+1]. If [f.sub.i+1] is oriented it completes the tower. If [f.sub.i+1] is blocked and the blocking edge is opposite to the edge shared with [f.sub.i] the construction of the potential tower can be extended. Otherwise, there is no tower starting with f.

We are ready to describe the tower Markov chain [M.sub.2T]. If [M.sub.2T] is in state [??] then it performs the transition to the next step as follows: an essential four-cycle f, and a p [member of] [0,1] are each chosen uniformly at random. If in [??] there is a tower [T.sub.f] of length k starting with f then revert [delta][T.sub.f] if

* [delta][T.sub.f] is clockwise and either k = 1 and p [less than or equal to] 1/2 or k > 1 and p [less than or equal to] 1/(4k),

* [delta][T.sub.f] is counterclockwise and either k = 1 and p < 1/2 or k > 1 and p [greater than or equal to] 1 - 1/(4k).

In all other cases the new state is again [??].

Since the steps of [M.sub.2] are also steps of [M.sub.2T] the chain is connected. In the orientation obtained by reverting the tower T = ([f.sub.1],..., [f.sub.k]) there is the tower T' = ([f.sub.k],..., [f.sub.1]) whose reversal leads back to the original orientation. Since both towers have the same length the chain is symmetric and its stationary distribution is uniform.

The next lemma is where the degree condition is indispensable.

Lemma 5 Let Q have maximum degree [LESS THAN OR EQUAL TO] 4 and let T = ([f.sub.1],..., [f.sub.k]) be a tower and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an oriented face in a 2-orientation Q of Q. If T and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] share an edge e but [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [f.sub.1] share no edge, then e is the edge of [f.sub.k] opposite to the blocking edge of [f.sub.k-1].

Proof. Let ([u.sub.i], [v.sub.i]) be the blocking edge of [f.sub.i]. We extend the labeling of vertices of T such that [partial derivative]T is the directed cycle [v.sub.0], [v.sub.1],..., [v.sub.k-1], [v.sub.k], [u.sub.k], [u.sub.k-1],..., [u.sub.1], [u.sub.0].

If ([u.sub.i+1], [u.sub.i]) with i [GREATER THAN OR EQUAL TO] 1 is an edge of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [??] contains an out-edge of [u.sub.i] which is not part of T. However, [u.sub.i] contains the out-edges ([u.sub.i], [v.sub.i]) and ([u.sub.i], [u.sub.i-1]). This contradicts outdeg([u.sub.i]) = 2.

If ([v.sub.i], [v.sub.i+1]) with i [greater than or equal to] 1 is an edge of [??] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [??] contains an in-edge of [v.sub.i] which is not part of T. Vertex [v.sub.i] also contains the in-edges ([u.sub.i], [v.sub.i]) and ([v.sub.i-1], [v.sub.i]). Now [v.sub.i] has in-degree [greater than or equal to] 3, since outdeg([v.sub.i]) = 2 the degree is at least 5. A contradiction.

We are not interested in edges shared by [??] and [f.sub.1], i.e, in edges containing [u.sub.0] or [v.sub.0]. Therefore, the only remaining candidate for e is the edge ([v.sub.k], [u.sub.k]).

Theorem 2 Let Q be a plane quadrangulation with n vertices so that each inner vertex is adjacent to at most 4 edges. The mixing time of [M.sub.2T] on 2-orientations of Q satisfies [[tau].sub.mix] [member of] O([n.sup.5]).

The proof of Theorem 2 is based on the path coupling theorem of Dyer and Greenhill [DG98]. Before stating a simple version of the Dyer--Greenhill Theorem we need a definition. A coupling for a Markov chain M on a state space Q is a pair ([X.sub.t], [Y.sub.t]) of processes satisfying two conditions:

* Each of ([X.sub.t]) and ([Y.sub.t]) represents M, i.e., Pr([Z.sub.t+1] = j|[Z.sub.t] = i) = [M.sub.i,j], for Z [member of] {X, Y} and all t.

* If [X.sub.t] = [Y.sub.t] then [X.sub.t+1] = [Y.sub.t+1].

Theorem 3 (Dyer-Greenhill) Let M be a Markov chain with state space [OMEGA]. If there is a graph [??] with vertex set [OMEGA] and a coupling ([X.sub.t], [Y.sub.t]) of M such that with the graph distance d : [OMEGA] X [OMEGA] [??] N based on [??] we have:

[??][d([X.sub.t+1], [Y.sub.t+1])] [less than or equal to] d([X.sub.t], [Y.sub.t]) and Pr(d([X.sub.t+1], [Y.sub.t+1]) [NOT EQUAL TO] d([X.sub.t], [Y.sub.t])) [greater than or equal to] [rho] then [[tau].sub.mix](M) [less than or equal to] 2[e/[rho]]diam[??].

The coupling of [M.sub.2T] used for the proof of Theorem 2 is the trivial one, i.e., we run chains [X.sub.t] and [Y.sub.t] with the same choices of f and p in each step.

The graph [??] will be the transition graph of [M.sub.2], i.e, the distance between 2-orientations X and Y equals the number of four-cycles that have to be reversed to get from X to Y.

Lemma 6 The maximum potential [p.sub.max] = ma[x.sub.f] p(f) of an essential cycle is less than n.

Proof. Let Q be the quadrangulation whose 2-orientations are in question. It is convenient to replace Q by Q# so that essential cycles are just faces. Recall that p of the outer face is 0 and |p (f) - p(f')| [less than or equal to] 1 for any two adjacent faces (Fact B). Since a quadrangulation has n - 2 faces we obtain (n - 3) as an upper bound for [p.sub.max].

Lemma 7 The diameter of [??] is at most [n.sup.2]/2.

Proof. The height of the lattice [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the length of a maximal flip sequence, i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using (Fact B) as in the proof of the previous lemma we find that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is < [n.sup.2]/2.

In the diagram of a distributive lattice the diameter is attained by the distance between the zero and the one, i.e., between the global minimum and the global maximum. This distance is exactly the height of the lattice. Since [??] is the cover graph (undirected diagram) of the distributive lattice [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we obtain that the diameter of [??] is at most [n.sup.2]/2.

3.2.1 Finding an appropriate [rho]

To get a reasonable [rho] the following argument is tempting and was actually used in [FR04] and [MRST12]: For given [??] and [??] there is always at least one essential cycle f whose reversal in [??] reduces the distance to [??]. If ([X.sub.t], [Y.sub.t]) = (X, Y) and this cycle f is chosen by [M.sub.2T], then with probability 1/2 the distance is reduced. There are at most n - 3 essential cycles. Hence we may set [rho] = 1 /(2n).

Indeed for up-down Markov chains on distributive such a statement holds. If I and J are down-sets of the poset P, then there is an x [member of] P whose addition to or removal from I decreases the distance to J. In the context of [alpha]-orientations, however, an f whose reversal in [??] reduces the distance to [??] may be oriented in [??] with the same orientation as in [??]. In that case if f is chosen by [M.sub.2T] the reversal of f is applied to both or to none Figure 5 shows that there are cases where a pairs ([X.sub.t], [Y.sub.t]) exists such that Pr(d([X.sub.t+1], [Y.sub.t+1]) [not equal to] d([X.sub.t], [Y.sub.t])) = 0.

To overcome this problem we now define the slow tower Markov chain [M.sub.S2T].

[FIGURE 5 OMITTED]

If [M.sub.S2T] is in state [??] then it performs the transition to the next step as follows: an essential four-cycle f, a value i with 0 [less than or equal to] i < n and a p [member of] [0, 1] are each chosen uniformly at random. If f is not at potential level i in [??], then nothing is done and [??] is the new state.

Otherwise, if there is a tower [T.sub.f] of length k starting with f then revert [partial derivative][T.sub.f] if

* [partial derivative][T.sub.f] is clockwise and either k = 1 and p [less than or equal to] 1/2 or k > 1 and p [less than or equal to] 1/(4k),

* [partial derivative][T.sub.f] is counterclockwise and either k = 1 and p > 1/2 or k > 1 and p [greater than or equal to] 1 - 1/(4k). In all other cases the new state is again [??].

Lemma 8 If ([X.sub.t], [Y.sub.t]) is a trivial coupling of the slow chain [M.sub.S2T], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. For given X and Y there is always at least one essential cycle [f.sub.1] whose reversal in X reduces the distance to [??]. If [f.sub.1] appears in [??] and [??] with the same orientation then the potential level of [f.sub.1] in [??] and [??] is different. Hence, if for the step of [M.sub.S2T] the triple (f, i, p) is chosen such that f = [f.sub.1] and i is the potential level of f in [??] and p is such that f is actually reversed, then the distance decreases.

The probability for choosing f is at least 1/n. For i and p the probabilities are 1/n and 1/2 respectively. Together this yields the claimed bound.

3.2.2 Completing the proof of Theorem 2

In Lemma 9 we show that if ([??], [??]) is an edge of [??] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the pair obtained after a single coupled step of the tower chain [M.sub.2T], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that a step of the coupled slow chain [M.sub.S2T] moves the pair ([??], [??]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with probability 1/n and otherwise stays at ([??], [??]). Hence Lemma 9 also applies to [M.sub.S2T].

Assuming Lemma 9 we get the following:

Proposition 1 Let Q be a plane quadrangulation with n vertices so that each inner vertex is adjacent to at most 4 edges. The mixing time of [M.sub.S2T] on 2-orientations of Q satisfies [[tau]mix]([M.sub.S2T]) [member of] O([n.sup.6])

Proof. For the condition E[d([X.sub.t+1], [Y.sub.t+1])] [less than or equal to] d([X.sub.t], [Y.sub.t]) needed for the application of Theorem 3 we need Lemma 9. The inequality from the lemma is also true for [M.sub.S2T] because this behaves like a slowed down version of [M.sub.2T]. Linearity of expectation allows to transfer the inequality from single edges to paths.

An application of Theorem 3 with parameters [rho] = 1/2[n.sup.2] (Lemma 8) and diam (G) [less than or equal to] [n.sup.2]/2 (Lemma 7) yields [[tau].sub.mix] ([M.sub.S2T]) [less than or equal to] e[n.sup.6].

The mixing time of the slow chain could thus be proven with a coupling that allows an application of the theorem of Dyer and Greenhill. Now consider a single state [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] evolving according to the slow chain [M.sub.S2T]. Note that this is exactly as if we would run the tower chain [M.sub.2T] but only allow a transition to be conducted if an additional uniform random variable q [member of] {0,..., n - 1} takes the value q = 0. It follows that the mixing times of [M.sub.S2T] and of [M.sub.2T] deviate by a factor of n. Therefore, [[tau].sub.mix]([M.sub.2T]) [less than or equal to] e[n.sup.5].

To complete the proof of Theorem 2 it remains to prove Lemma 9.

Lemma 9 If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an edge of [??] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the pair obtained after a single coupled step of [M.sub.2T], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Since ([??], [??]) is an edge of [??] they differ in the orientation of exactly one face [??]. We assume w.l.o.g that [??] is oriented clockwise in [??] and counterclockwise in [??].

Let f be the face chosen for the step of [M.sub.2T]. Depending on f we analyze [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in three cases.

A. If f = [??], then depending on the value of p face f is reversed either in [??] or in [??]. After the step the orientations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] coincide. The expected change of distance in this case is -1.

B. If f and [??] share an edge and f [not equal to] [??] there are three options depending on the type of f in [??].

1. Face f is oriented in [??], necessarily clockwise. It follows that in [??] face f starts the clockwise tower (f, [??]) of length two. In [??] a face f is a clockwise tower of length 1. If p [less than or equal to] 1/8 both towers are reversed so that [??] and [??] coincide. If 1/8 < p [less than or equal to] 1/2, then f is reversed in Y while [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in this case the distance increases by 1. If p > 1/2 both orientations remain unchanged. The expected change of distance in this case is 1/8 X (-1) + (1/2 - 1/8) x (+1) + 1/2 X 0 = 1/4.

2. Face f is scrambled in Y. In this case f is blocked in X and it may start a tower of length k. If p [less than or equal to] 1/(4k) this tower is reverted which results in a increase of distance by k. In all other cases the distance remains unchanged. Hence, the expected change of distance in this case is [less than or equal to] 1/4.

3. Face f is blocked in [??]. Then it is either oriented or scrambled in [??]. After changing the role of [??] and [??] we can use the analysis of the other two cases to conclude that the expected change of distance is again [less than or equal to] 1/4.

C. Finally, suppose that f and [??] have no edge in common.

1. If f starts a tower in [??] which has no edge in common with [??], then f starts the very same tower in [??] and the coupled chain will either revert both towers or none of them. The distance remains unchanged.

2. Now let f start a tower T = ([f.sub.1],..., [f.sub.k]) in [??] which has an edge in common with [??]. The case where [??] and [f.sub.1] = f share an edge was considered in B. Now Lemma 5 implies that either [??] = [f.sub.k] or [??] [not equal to] [f.sub.k] and the shared edge is such that ([f.sub.1],..., [f.sub.k], [??]) is a tower in [??]. Hence, with T there is a tower T' in [??] that starts in f and has length k [+ or -] 1, moreover T and T' have the same orientation. Let [??] be the larger of the lengths of T and T'. With a probability of 1/(4[??]) both towers are reversed and the distance decreases by 1. With a probability of 1/(4([??] - 1)) - 1/(4[??]) only the shorter of the two towers is reversed and the distance increases by [??] - 1. With the remaining probability both orientations remain unchanged. The expected change of distance in this case is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let m be the number of essential four-cycles, i.e., the number of options for f. Combining the values for the change of distance in cases A, B, C and the probability of these cases we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.3 Comparison of [M.sub.2T] and [M.sub.2]

The comparison of the mixing times of [M.sub.2T] and [M.sub.2] is based on a technique developed by Diaconis and Saloff-Coste [DSC93]. We will use Theorem 4 a variant due to Randall and Tetali [RT97].

Let M and [??] be two reversible Markov chains on the same state space [OMEGA] such that M and [??] have the same stationary distribution [pi]. With E(M) we denote the edges of the directed transition graph of M, i.e, (x, y) [member of] E(M) whenever M(x, y)4 > 0. Define E([??]) alike. For each (x, y) [member of] E([??]) define a canonical path [[gamma].sub.xy] as a sequence x = [v.sub.0], [v.sub.1],..., [v.sub.k] = y of transitions of M, i.e. ([v.sub.i], [v.sub.i+1]) [member of] E(M) for all i. Let |[[gamma].sub.xy]| be the length of [[gamma].sub.xy] and for (x, y) [member of] E(M) let [GAMMA](x, y) := {(u, v) [member of] E([??]) : (x, y) [member of] [[gamma].sub.uv]}. Further let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and let [pi]*: = mi[n.sub.x[member of][OMEGA]] [pi](x).

Theorem 4 (Randall-Tetali) In the above setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We are going to apply this theorem with M = [M.sub.2] and [??] = [M.sub.2T]. Both chains are symmetric, hence reversible, and have the uniform distribution [pi] as stationary distribution.

The definition of the canonical paths comes quite natural. A transition ([??], [??]) of [M.sub.2T] corresponds to the reversal of [partial derivative]T for some tower T of [??]. Suppose that T = ([f.sub.1],..., [f.sub.k]) and recall that the effect of reverting [partial derivative]T can also be obtained by reverting [f.sub.k], [f.sub.k-1],..., [f.sub.1] in this order. Reverting them one by one yields a path in E(M), this path is chosen to be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], i.e., the transition ([??], [??]) corresponds to a tower of length k, then [M.sub.2T]([??], [??]) = 1/(4k), hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Also [pi] is constant so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For an upper bound on [??] we therefore only have to estimate the number of tower moves that have a canonical path that contains the face flip at [??] that moves [??] to [??]. If T = ([f.sub.1],..., [f.sub.k]) is such a tower with f = [f.sub.i], then ([f.sub.1],..., [f.sub.i-1], f) is a tower in [??] and ([f.sub.k],..., [f.sub.i+1], f) is a tower in [??]. Since a tower is defined by its initial face each of [??] and [??] has at most n towers, all the more each has at most n towers ending in f. This shows [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [??] [less than or equal to] [n.sup.2]/4.

It remains to find [pi]* = 1/|[OMEGA]|. Since a quadrangulation has 2n - 4 edges it has at most [2.sup.2n] orientations this would suffice for our purposes. However, a better upper bound of 1.[9.sup.n] for the number of 2-orientations was obtained in [FZ08].

Given the above ingredients for the comparison theorem and the mixing time of [[tau].sub.mix]([M.sub.2T]) [member of] O([n.sup.5]) from Theorem 2 we finally have shown rapid mixing for [M.sub.2] on certain quadrangulations.

Theorem 5 Let Q be a plane quadrangulation with n vertices so that each inner vertex is adjacent to at most 4 edges. The mixing time of the face reversal Markov chain [M.sub.2] on 2-orientations of Q satisfies [[tau].sub.mix]([M.sub.2]) [member of] O([n.sup.8]).

4 Slow mixing for 3-orientations

A triangulation is a plane graphs whose faces are uniformly of degree 3. Equivalently triangulations are triangulation maximal plane graphs.

A 3-orientation of a triangulation T is an orientation of the internal edges, i.e., of the edges except the three edges of the outer face, such that outdeg(v) = 3 for all inner vertices v. Since a triangulation with n vertices has 3n - 9 inner edges it follows that the three outer vertices are sinks.

A Schnyder wood of T is an orientation and coloring of the edges of T with colors red, green, and blue such that two conditions hold:

(1) If the vertices of the outer face are colored red, green and blue in clockwise order, then all inner edges incident to a vertex s of the outer face are oriented towards s and colored in the color of s.

(2) Every inner vertex v has three outgoing edges colored red, green, and blue in clockwise order. Incoming edges in the sector between two outgoing edges are colored in the third color (see Figure 2).

[FIGURE 6 OMITTED]

Schnyder woods were introduced by Schnyder in [Sch89]. We refer to [dFOdM01, PS06, Fel04a, AB[F.sup.+]13] and the references given there for properties, applications and generalizations of Schnyder woods. Relevant to us is the following fact, see [dFOdM01]:

Fact 3. The forget function that associates a 3-orientation with a Schnyder wood is a bijection between the set of 3-orientations and the set of Schnyder woods of a triangulation.

From the correspondence between Schnyder woods and 3-orientations it follows that the triangle flip Markov chain can be used to sample from either of these structures. The mixing time of this Markov chain was studied by Creed [Cre09] for certain subgraphs of the triangular grid and then By Miracle et al. [MRST16] for general triangulations. Here we want to revisit the following negative result.

Theorem 6 (Miracle--Randall--Streib--Tetali) There is a triangulation [T'.sub.n] with 4n + 1 vertices with maximum degree 2n + 3 such that the triangle flip Markov chain [M.sub.3] on 3-orientations of [T'.sub.n] has [[tau].sub.mix] > 1/16 [2.sup.n/4].

With Theorem 7 we prove a similar result with a larger exponential bound on [[tau].sub.mix]. Moreover, [T.sub.n] is simpler than [T'.sub.n]. This carries over to the simplicity of the proof. In fact the proof is very similar to the proof for Theorem 1. Below, in Proposition 2 we modify [T.sub.n] to show that slow mixing of the triangle flip chain [M.sub.3] can also be observed for triangulations with maximum degree in the order of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 7 Let [T.sub.n] be the triangulation on 3n+4 vertices with maximum degree 2n+3 shown in Figure 7. The triangle flip Markov chain [M.sub.3] on 3-orientations of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 7 OMITTED]

Proof. Let [OMEGA] be the set of Schnyder woods of [T.sub.n]. We define a hour glass partition [[OMEGA].sub.L], [[OMEGA].sub.c], [[OMEGA].sub.R] of this set. The edges ([x.sub.0], [a.sub.g]) and ([x.sub.0], [a.sub.b]) are rigid, the red out-edge ([x.sub.0], z) of [x.sub.0] is called left if z [member of] {[v.sub.1],..., [v.sub.n]}, it is right if z [member of] {[w.sub.1],..., [w.sub.n]} and it is central if z = [x.sub.1]. Now [[OMEGA].sub.L], [[OMEGA].sub.C], [[OMEGA].sub.R] are the sets Schnyder woods where the red edge of [x.sub.0] is left, central, and right respectively. With the next claim we show that this is a hour glass partition.

Claim 1. If [S.sub.1] [member of] [[OMEGA].sub.L] and [S.sub.2] [member of] [[OMEGA].sub.R], the [M.sub.2]([S.sub.1], [S.sub.2]) = 0.

If S [right arrow] S' is a step of [M.sub.3] which changes the red out-edge [??] of [x.sub.0], then the step corresponds to the reversal of a triangle containing [??]. There is no triangle in [T.sub.n] with vertices {[x.sub.0],[v.sub.i], [w.sub.j]} for i, j [member of] [n]. Hence, if S [member of] [[OMEGA].sub.L], then S' [member of] [[OMEGA].sub.L] [??] [[OMEGA].sub.C].

Claim 2. |[[OMEGA].sub.C]| = 1 and Figure 7 shows the unique Schnyder wood of this set.

Consider S [member of] [[OMEGA].sub.C]. From ([x.sub.0], [x.sub.1]) [member of] S we conclude that {[v.sub.1], [x.sub.2], [w.sub.1]} are the out-neighbors of [x.sub.1]. From the degrees it follows that all the edges between {[v.sub.1], [x.sub.2], [w.sub.1]} and {[v.sub.2], [x.sub.3], [w.sub.2]} are oriented upward in S. Inductively we find that all the edges between {[v.sub.i-1], [x.sub.i], [w.sub.i-1]} and {[v.sub.i], [x.sub.i+1], [w.sub.i]} are oriented upward in S. Since the edges ([v.sub.i], [x.sub.0]) and ([w.sub.i], [x.sub.0]) are in S anyway it follows that the orientation of all edges is fixed when ([x.sub.0], [x.sub.1]) is fixed. The bijection between 3-orientations and Schnyder woods then yields that the Schnyder wood shown in Figure 7 is the unique element of [[OMEGA].sub.C].

Claim 3. |[[OMEGA].sub.L]| = |[[OMEGA].sub.R]| > [(2 + [??]).sup.n-1].

From the symmetry of [T.sub.n] we easily get that |[[OMEGA].sub.L]| = |[[OMEGA].sub.R]|. Now let [P.sub.k] be the set of directed path from [x.sub.0] to [v.sub.k] in the orientation S from Figure 7. If p [member of] [P.sub.k] then ([v.sub.k], [x.sub.0]) together with p forms a directed cycle in S. Reverting this cycle yields a 3-orientation that contains the edge ([x.sub.0], [v.sub.k]). This 3-orientation belongs to [[OMEGA].sub.L]. Different paths in [P.sub.k] yield different orientations. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (in fact equality holds).

It remains to evaluate [g.sub.k] = |[P.sub.k]|. To do so let [h.sub.k] be the number of directed paths from [x.sub.0] to [x.sub.k]. Clearly, [h.sub.k+1] = [h.sub.k] + 2[g.sub.k] and [g.sub.k+1] = [h.sub.k+1] + [g.sub.k] with initial conditions [h.sub.1] = [g.sub.1] = 1. Standard techniques for solving linear recurrences yield

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The claim now follows from |[[OMEGA].sub.L]| > |[P.sub.k]| = [g.sub.n] > [(2 + [??]).sup.n-1].

The three claims together with Lemma 1 yield [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Which implies the theorem via Fact T.

4.1 Slow mixing for 3-orientations with sub-linear maximum degree

As announced we now modify [T.sub.n] to prove slow mixing for Schnyder woods of triangulations with a sub-linear maximum degree. For a given m [member of] [??] the triangulation [T.sub.n] (m) is constructed by replacing each edge {[x.sub.i], [x.sub.i+1]} with i [greater than or equal to] 1 by a path [x.sub.i], [y.sub.i],1,..., [y.sub.i],m, [x.sub.i+1]. Each vertex [y.sub.i,j] is also made adjacent to to [v.sub.i] and [w.sub.i], see Figure 8. The resulting triangulation [T.sub.n](m) has 3n + 4 + (n - 1)m vertices and its maximum degree is max{2n + 3, m + 5}.

[FIGURE 8 OMITTED]

The definition of [[OMEGA].sub.L], [[OMEGA].sub.c], [[OMEGA].sub.R] for [T.sub.n](m) is the same as for [T.sub.n]. This is again a hour glass partition, i.e., there is no direct transition between [[OMEGA].sub.L] and [[OMEGA].sub.R]. Replacing the red edges ([x.sub.i], [x.sub.i+1]) in Figure 7 by the colored gadget of Figure 8 yields the unique Schnyder wood S of [[OMEGA].sub.c]. To estimate |[[OMEGA].sub.L]| we again look at the set [P.sub.n] of directed paths from [x.sub.0] to [x.sub.n] in S. Since there are 2m + 3 directed path from [x.sub.i] to [x.sub.i+1] we get |[P.sub.n]| > [(2m + 3).sup.n-1]. From |[[OMEGA].sub.L]| > [(2m).sup.n-1] we obtain:

Proposition 2 Let [T.sub.n](2n) be the above triangulation on 2[n.sup.2] + n + 4 vertices with maximum degree 2n + 5. The triangle flip Markov chain [M.sub.3] on 3-orientations of the triangulation [T.sub.n](n) has [[tau]sub.mix] > [2.sup.(n-1) log(4n)-2].

4.2 Slow mixing for [alpha]-orientations with constant degree

In [MRST16] and in this paper there are proofs for rapid mixing of the face flip Markov chain for [alpha]-orientations on graphs with small constant maximum degree and negative results in the sense of slow mixing of these Markov chains for graphs with large maximum degree. Could it be that the face flip Markov chain for [alpha]-orientations is rapidly mixing for all graphs of small maximum degree? In this subsection we show that this is not the case.

Our example family [G.sub.k] is obtained from [T.sub.3k-2]. In [T.sub.3k-2] remove all edges incident to [x.sub.0] except those connecting to [a.sub.g] and [a.sub.b]. Let [H.sub.k] be a patch taken from the triangular grid whose boundary is a regular hexagon with side length k, i.e., each side has k + 1 vertices, and in total [H.sub.k] has 3([k.sup.2] + k) + 1 vertices. Now identify two opposite corners of [H.sub.k] with the vertices [x.sub.0] and [x.sub.1] of [T.sub.3k-2]. Label the vertices on the left boundary of [H.sub.k] as [v'.sub.0] = [x.sub.1], [v'.sub.1],..., [v'.sub.3k-4], [v'.sub.3k-3] = [x.sub.0] and on the right boundary as [w'.sub.0] = [x.sub.1], [w'.sub.1],..., [w'.sub.3k-4], [w'.sub.3k-3] = [x.sub.0]. Add the missing edges to make [v.sub.i], [v'.sub.i], [v'.sub.i+1] and [w.sub.i], [w'.sub.i], [w'.sub.i+1] triangles for i = 1, ... 3k - 2. Finally add the edges from [v'.sub.3k-1] to [a.sub.b] and from [w'.sub.3k-1] to [a.sub.g]. Figure 9 shows the result of the construction for k = 3.

The graph [G.sub.k] has 3([k.sup.2] + 4k - 1) vertices, the degrees are between 4 and 6. Let [alpha] be the function shown on the right part of Figure 9, the values taken by [alpha] range from 0 to 5. A key property of [alpha] is that except from the rigid edges which connect to [a.sub.g] and [a.sub.b] there is exactly one out-edge of [H.sub.k], i.e., one edge directed from a vertex of [H.sub.k] to a vertex outside of [H.sub.k].

Let [OMEGA] denote the set of a-orientation of [G.sub.k] We define a hour glass partition [[OMEGA].sub.L], [[OMEGA].sub.c], [[OMEGA].sub.R] of this set. Let (y, z) be the unique non-rigid out-edge of [H.sub.k]. The edge (y, z) is called left if z [member of] {[v.sub.1],..., [v.sub.n]}, it is right if z [member of] {[w.sub.1],..., [w.sub.n]} and it is central if z = [x.sub.1]. Now [[OMEGA].sub.L], [[OMEGA].sub.c], [[OMEGA].sub.R] are the [alpha]-orientations where the edge (y, z) is left, central, and right respectively.

It is clear that there is no transition between elements of [[OMEGA].sub.L] and [[OMEGA].sub.R], i.e., the partition has the hour glass property. The set [[OMEGA].sub.c] has precisely one element, this is the orientation shown in Figure 9. The size of [[OMEGA].sub.L] is at least as large as the size of the set for [T.sub.3k-2] which has been shown to be > 3.7[3.sup.3k-4]. With the implied bound on the conductance and Fact T we obtain our last theorem.

Theorem 8 The triangulation [G.sub.k] on 3([k.sup.2] + 4k - 1) vertices with maximum degree 6 and the function [alpha] shown in Figure 9 have a slow mixing face flip Markov chain [M.sub.[alpha]], more precisely [[tau].sub.mix]([M.sub.[alpha]]) > 3.7[3.sup.3(k-2)].

References

[AB[F.sup.+]13] Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, and Torsten Ueckerdt. Computing cartograms with optimal complexity. Discr. and Comput. Geom., 50:784-810, 2013.

[BH12] Lali Barriere and Clemens Huemer. 4-labelings and grid embeddings of plane quadrangulations. Discr. Math., 312:1722-1731, 2012.

[FIGURE 9 OMITTED]

[BSVV08] Ivona Bezakova, Daniel Stefankovic, Vijay V. Vazirani, and Eric Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM J. Comput., 37:1429-1454, 2008.

[Cre09] Paidi J. Creed. Sampling Eulerian orientations of triangular lattice graphs. J. of Discr. Alg., 7:168-180, 2009.

[dFOdM01] Hubert de Fraysseix and Patrice Ossona de Mendez. On topological aspects of orientations. Discr. Math., 229:57-72, 2001.

[DG98] Martin Dyer and Catharine Greenhill. A more rapidly mixing Markov chain for graph colourings. Rand. Struct. and Alg., 13:285-317, 1998.

[DSC93] Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible Markov chains. An. of Appl. Prob., 3:696-730, 1993.

[Fel04a] S. Felsner. Geometric Graphs and Arrangements. Vieweg Verlag, 2004.

[Fel04b] Stefan Felsner. Lattice structures from planar graphs. Electr. J. Combin., 11(1):24p., 2004.

[FFNO11] Stefan Felsner, Eric Fusy, Marc Noy, and David Orden. Bijections for Baxter families and related objects. J. Combin. Theory Ser. A, 18:993-1020, 2011.

[FHKO10] Stefan Felsner, Clemens Huemer, Sarah Kappes, and David Orden. Binary labelings for plane quadrangulations and their relatives. Discr. Math. and Theor. Comp. Sci., 12:3:115-138, 2010.

[FK09] Stefan Felsner and Kolja Knauer. ULD-lattices and [DELTA]-bonds. Comb., Probab. and Comput., 18(5):707-724, 2009.

[FR04] Johannes Fehrenbach and Ludger Ruschendorf. Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional cartesian grids. Statistics & Decisions, 22:109-130, 2004.

[FZ08] Stefan Felsner and Florian Zickfeld. On the number of planar orientations with prescribed degrees. Electr. J. Combin., 15:41p., 2008.

[JSV04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51:671-697, 2004.

[LPW09] David Levin, Yuval Peres, and Elizabeth Wilmer. Markov Chains and Mixing Times. AMS, 2009.

[LRS95] M. Luby, D. Randall, and A. Sinclair. Markov chain algorithms for planar lattice structures. In Proc. FOCS, pages 150-159, 1995.

[MRST12] Sarah Miracle, Dana Randall, Amanda Pascoe Streib, and Prasad Tetali. Mixing times of Markov chains on 3-orientations of planar triangulations. In Proc. A of A' 12, Proc. AQ, pages 413-424. Discr. Math. and Theor. Comp. Sci., 2012. full version arXiv:1202.4945.

[MRST16] Sarah Miracle, Dana Randall, Amanda Pascoe Streib, and Prasad Tetali. Sampling and counting 3-orientations of planar triangulations. SIAM J. Discr. Math., 30:801-831, 2016.

[MW96] Milena Mihail and Peter Winkler. On the number of Eulerian orientations of a graph. Algorithmica, 16:402-414, 1996.

[Pro97] James Propp. Generating random elements of finite distributive lattices. Electr. J. Combin., 4:12 pp., 1997.

[PS06] D. Poulalhon and G. Schaeffer. Optimal coding and sampling of triangulations. Algorithmica, 46:505-527, 2006.

[PW96] James G. Propp and David B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Rand. Struct. and Alg., 9(1&2):223-252, 1996.

[RT97] Dana Randall and Prasad Tetali. Analyzing Glauber dynamics by comparison of Markov chains. J. of Math. Phys., 41:1598-1615, 1997.

[Sch89] W. Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989.

[SJ89] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput., 82:93-133, 1989.

Stefan Felsner (*)

Institut fur Mathematik, Technische Universitat Berlin

received 10th Feb. 2016, accepted 5th Dec. 2016.

(*) Partially supported by DFG FE-340/11-1
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Felsner, Stefan; Heldt, Daniel
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Nov 1, 2016
Words:10623
Previous Article:Ramsey-type theorems for lines in 3-space.
Next Article:Combinatorial optimization in networks with Shared Risk Link Groups.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |