Georgia Institute of Technology College of Sciences

We consider perfect matchings of the square-octagon lattice, also known as``fortresses.'' There is a natural local Markov chain on the setof perfect matchings that is known to be ergodic. However, unlike Markov chains for sampling perfect matchings on the square and hexagonallattices, corresponding to domino and lozenge tilings, respectively, the seemingly relatedMarkov chain on the square-octagon lattice appears to converge slowly. Tounderstand why, we consider a weighted version of the problem.As with domino and lozenge tilings, it will be useful to view perfectmatchings on the square-octagon lattice in terms of sets of paths and cycleson a corresponding lattice region; here, the paths and cycles lie on theCartesian lattice and are required to turn left or right at every step. Forinput parameters $\lambda$ and $\mu$, we define the weight of a configurationto be $\lambda^{\abs{E(\sigma)}} \mu^{\abs{V(\sigma)}},$ where $E(\sigma)$ isthe total number of edges on the paths and cycles of $\sigma$ and $V(\sigma)$is the number of vertices that are not incident to any of the paths or cyclesin $\sigma$. Weighted paths already come up in the reduction from perfectmatchings to turning lattice paths, corresponding to the case when $\lambda=1$and $\mu = 2$.First, fixing $\mu=1$, we show that there are choices of~$\lambda$ for whichthe chain converges slowly and another for which it is fast, suggesting a phasechange in the mixing time. More precisely,the chain requires exponential time (in the size of the lattice region) when$\lambda < 1/(2\sqrt{e})$ or $\lambda >2\sqrt{e}$, while it is polynomially mixingat $\lambda = 1$. Further, we show that for $\mu>1$, the Markov chain $\m$ is slowly mixingwhen $\lambda < \sqrt{\mu}/(2\sqrt{e})$ or $\lambda > 2\mu\sqrt{e}$. These arethe first rigorous proofs explaining why the natural local Markov chain can beslow for weighted fortresses or perfect matchings on thesquare-octagon lattice.