| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Edge-flip chains

    1. Edge-flip chain on dyadic tilings and rectangular dissections (Sarah Cannon)

          Consider rectangular dissections of an $n\times n$ lattice into $n$ rectangles of area $n$, where $n=2^k$. The edge-flip chain proceeds by picking an edge bordering two rectangles and replacing it by its bisector. In the dyadic case, the edge is flipped provided the resulting tiling remains dyadic. In the weighted setting, a parameter $\lambda>0$ is fixed, and the weight of a dissection is given by $$ \pi(\sigma)=\frac{\lambda^{|\sigma |}}{Z} , $$ where $|\sigma|$ is the total edge-length. The chains (in the dyadic and general cases) then correspond to the Glauber dynamics.

      Add remark

      Problem 2.1.

      [Sarah Cannon] For $\lambda=1$, can we establish a polynomial upper-bound (fast-mixing) for the mixing time of the edge-flip chain on dyadic tilings or on rectangular dissections?
          Known lower-bound $O(n\log n)$ for dyadic tilings with $\lambda=1$. In the dyadic case, the edge-flip chain is known to be fast-mixing $O(n^2\log n)$ for $\lambda<1$ and slow-mixing $\exp(\Omega(n^2))$ for $\lambda>1$. In the general case, the chain is slowly mixing both for $\lambda<1$ and $\lambda>1$.

      References:

      - Sarah Cannon, Sarah Miracle, and Dana Randall, "Phase Transitions in Random Dyadic Tilings and Rectangular Dissections".

      - Svante Janson, Dana Randall, and Joel Spencer, "Random dyadic tilings of the unit square".

      - Mike Korm, PhD thesis, Chapter 7.

        • Edge-flip chain on triangulations


          Add remark

          Problem 2.2.

          [Alexandre Stauffer] Consider the chain over triangulations of $[0,n]^2$, in which, at each step, an edge is randomly chosen and, if it is the diagonal of convex quadrilateral, flipped to the opposite diagonal. Does this chain have polynomial mixing time?
              Known lower bound $O(n^3)$, given by the diameter. Upper-bound $\exp(\Omega(n^2))$.

          References:

          - Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer, "Random lattice triangulations".

          - Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer, "Dynamics of Lattice Triangulations on Thin Rectangles".

          - Alexandre Stauffer, "A Lyapunov function for Glauber dynamics on lattice triangulations".

            • Edge-flip on triangulations of a convex polygon


              Add remark

              Problem 2.3.

              [Emma Cohen] Consider the random walk on triangulations of a convex polygon, driven by flips of a randomly chosen diagonal. What is the mixing time?
                  Known lower bound $\Omega(n^{3/2})$, by Molloy, Reed, Steiger (1998). Known upper bound $O(n^5\log n)$, by McShine and Tetali. Conjecture: the lower bound gives the right order.

                • Random walks on Dyck’s paths


                  Add remark

                  Problem 2.4.

                  [Emma Cohen] Consider the Markov chain on the set of Dyck’s paths, which moves by choosing uniformly at random two coordinates and exchanging their value ($+$ or $-1$) provided the resulting path remains a Dyck’s path. What is the mixing time?
                      Cohen, Tetali, Yeliussizov (2015) showed a lower bound of $\Omega(n)$ and an upper bound of $O(n^2\log n)$.

                      Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.