[math-fun] Random domino tiling.
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. Mathologer didn't say it, but this gives a reasonably efficient way to generate a random tiling of any tilable simply-connected polyomino P. Procedure: use the magic determinant to count how many tilings of P there are; call this N, and pick a random number K between 0 and N-1. This will be the "index" of the random tiling we will select. Now, prune off all the parts that have their domino coverings forced in some way or other. In the part that's left, pick the leftmost cell of the topmost row: it can be covered in exactly two ways, horizontally, and vertically. Imagine it's horizontal, and remove that domino to get a new polyomino Ph. Count how many tilings of Ph there are; call that N'. If K < N', then that upper-left cell will be covered horizontally; if K >= N', it will be covered vertically (and the remaining polyomino we will call Pv). Now repeat this procedure with index K and polyomino Ph, or with index K-N' and polyomino Pv, depending on the outcome of the comparison. Eventually you will have tiled all the cells. I would like to see an app that takes a given polyomino and picks random tilings for you. I would also like to see one that colors the cells of a given polyomino by the probability that they are covered horizontally or vertically by a random tiling.
This would be much nicer if there was a good way to calculate the determinant. On Sat, Dec 26, 2020 at 6:44 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.
Mathologer didn't say it, but this gives a reasonably efficient way to generate a random tiling of any tilable simply-connected polyomino P. Procedure: use the magic determinant to count how many tilings of P there are; call this N, and pick a random number K between 0 and N-1. This will be the "index" of the random tiling we will select. Now, prune off all the parts that have their domino coverings forced in some way or other. In the part that's left, pick the leftmost cell of the topmost row: it can be covered in exactly two ways, horizontally, and vertically. Imagine it's horizontal, and remove that domino to get a new polyomino Ph. Count how many tilings of Ph there are; call that N'. If K < N', then that upper-left cell will be covered horizontally; if K >= N', it will be covered vertically (and the remaining polyomino we will call Pv).
Now repeat this procedure with index K and polyomino Ph, or with index K-N' and polyomino Pv, depending on the outcome of the comparison. Eventually you will have tiled all the cells.
I would like to see an app that takes a given polyomino and picks random tilings for you. I would also like to see one that colors the cells of a given polyomino by the probability that they are covered horizontally or vertically by a random tiling. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ -
Determinant finding is expensive, but not so expensive as to make this algorithm impractical for chessboard-sized polyominoes, I suspect. The adjacency matrix, remember, is pretty darned sparse, and I think we have good determinant-finders for sparse cases. On Sat, Dec 26, 2020 at 9:52 PM Tomas Rokicki <rokicki@gmail.com> wrote:
This would be much nicer if there was a good way to calculate the determinant.
On Sat, Dec 26, 2020 at 6:44 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.
Mathologer didn't say it, but this gives a reasonably efficient way to generate a random tiling of any tilable simply-connected polyomino P. Procedure: use the magic determinant to count how many tilings of P there are; call this N, and pick a random number K between 0 and N-1. This will be the "index" of the random tiling we will select. Now, prune off all the parts that have their domino coverings forced in some way or other. In the part that's left, pick the leftmost cell of the topmost row: it can be covered in exactly two ways, horizontally, and vertically. Imagine it's horizontal, and remove that domino to get a new polyomino Ph. Count how many tilings of Ph there are; call that N'. If K < N', then that upper-left cell will be covered horizontally; if K >= N', it will be covered vertically (and the remaining polyomino we will call Pv).
Now repeat this procedure with index K and polyomino Ph, or with index K-N' and polyomino Pv, depending on the outcome of the comparison. Eventually you will have tiled all the cells.
I would like to see an app that takes a given polyomino and picks random tilings for you. I would also like to see one that colors the cells of a given polyomino by the probability that they are covered horizontally or vertically by a random tiling. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ - _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks, I think I spoke too quickly; it's been a while. I think there are good algorithms these days---LU decomposition in prime fields will probably be efficient and accurate enough for interesting results. -tom On Sat, Dec 26, 2020 at 6:55 PM Allan Wechsler <acwacw@gmail.com> wrote:
Determinant finding is expensive, but not so expensive as to make this algorithm impractical for chessboard-sized polyominoes, I suspect. The adjacency matrix, remember, is pretty darned sparse, and I think we have good determinant-finders for sparse cases.
On Sat, Dec 26, 2020 at 9:52 PM Tomas Rokicki <rokicki@gmail.com> wrote:
This would be much nicer if there was a good way to calculate the determinant.
On Sat, Dec 26, 2020 at 6:44 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.
Mathologer didn't say it, but this gives a reasonably efficient way to generate a random tiling of any tilable simply-connected polyomino P. Procedure: use the magic determinant to count how many tilings of P there are; call this N, and pick a random number K between 0 and N-1. This will be the "index" of the random tiling we will select. Now, prune off all the parts that have their domino coverings forced in some way or other. In the part that's left, pick the leftmost cell of the topmost row: it can be covered in exactly two ways, horizontally, and vertically. Imagine it's horizontal, and remove that domino to get a new polyomino Ph. Count how many tilings of Ph there are; call that N'. If K < N', then that upper-left cell will be covered horizontally; if K >= N', it will be covered vertically (and the remaining polyomino we will call Pv).
Now repeat this procedure with index K and polyomino Ph, or with index K-N' and polyomino Pv, depending on the outcome of the comparison. Eventually you will have tiled all the cells.
I would like to see an app that takes a given polyomino and picks random tilings for you. I would also like to see one that colors the cells of a given polyomino by the probability that they are covered horizontally or vertically by a random tiling. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ - _______________________________________________ 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
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ -
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.
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
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
participants (4)
-
Allan Wechsler -
Dan Asimov -
James Propp -
Tomas Rokicki