4
$\begingroup$

Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of dimer covers (aka perfect matchings) of this graph into the state space of a Markov chain whose moves consist of rotating edges around a random face (assuming that the vertices around that face are matched with each other, and doing nothing otherwise), then the mixing time is exponential in $n$ - despite the fact that we have rapid mixing results for dimer covers of the square grid and the hexagonal grid (due to work of Luby, Randall, Sinclair, Wilson, and perhaps others I'm neglecting to mention; I'll include more names here if people remind me whom to acknowledge).

And we even sort of "know" why the local differences in the structure of these graphs makes such a big difference for the mixing time.

But has anyone actually proved it?

I'd be happiest with an answer for the fortress graphs, but nearly as happy for a rigorous proof of slow mixing for some other family of subgraphs of the square-octagon graph.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.