Allan's method is a pretty good way to generate random tilings, and back in the 90s David B. Wilson came up with ways to make it even better by exploiting commonalities between the many matrices whose determinants must be found. (I can't remember his bound on the running time; maybe cubic in the number of vertices?) My favorite approach to generating random objects is Coupling From The Past, developed by Wilson and me. It applies not only to random domino tilings but also to other combinatorial objects such as alternating sign matrices for which analogues of Allan's method run aground on the difficulty of exact enumeration of subconfigurations. Thurston's approach to domino tilings is described in his article "Conway's Tiling Groups" which fortunately can be found on the web (e.g. at https://www.cimat.mx/~gil/ciencia_para_jovenes/pensamiento_matematico/thurst...). I'm currently writing an article about this stuff for the Mathematical Intelligencer's upcoming Conway memorial issue. There are programs for generating random tilings; see http://faculty.uml.edu/jpropp/software.html . Jim On Sat, Dec 26, 2020 at 9:59 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ask and ye shall receive. Mathologer walks through a proof sketch at the end of this video: https://www.youtube.com/watch?v=Yy7Q8IWNfHM&t=2351s.
On Sat, Dec 26, 2020 at 9:54 PM Dan Asimov <asimov@msri.org> wrote:
I'd like to see (or figure out) a proof of that determinant-count principle.
Also, I recall vaguely that on math-fun ca. 20 years ago, Bill Thurston was talking about some clever insight he had into domino tilings of plane regions. I wonder if someone can look into math-fun archives and re-post his comments.
—Dan
On Saturday/26December/2020, at 6:43 PM, Allan Wechsler < acwacw@gmail.com> wrote:
Today I learned from a Mathologer video (Burkard Polster, who apparently knows funster Jim Propp), that there is a fairly simple formula for the number of domino tilings on an arbitrary simply-connected polyomino. (Mathologer was ambiguous about whether the formula fails when the polyomino has narrow "necks", but my guess is that these cases are fine.)
You checkerboard-color the thing. In order for there to be any tilings at all, there have to be an equal number n of black and white squares. Then, assigning columns to white and rows to black, you construct an adjacency matrix; horizontal connections are marked 1, vertical connections are marked i (!), with 0's elsewhere; and then finally you take the determinant. Magically, either the entire real part or the entire imaginary part cancels away, and the absolute coefficient of the result (either pure imaginary or pure real) is the number of tilings.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun