Timeline for Random self-avoiding lattice cycle within a given bounding box
Current License: CC BY-SA 2.5
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2011 at 1:02 | comment | added | Sasho Nikolov | @bbejot: it was silly of me not to see that. ok, nevermind..i was thinking about the standard random walk method of generating random spanning trees, btw. | |
| May 6, 2011 at 0:18 | comment | added | bbejot | @Sasho, your algorithm would have to be modified so that it always yielded a cycle. As it currently is, you could have a repeated vertex on the circuit surrounding the $k$ cells. Also, it could create multiple independent cycles by enclosing 1 or more cells. | |
| May 5, 2011 at 20:02 | comment | added | Sasho Nikolov | Here is a heuristic idea with no justification that it should work: do a random walk on the squares for some number of steps, say much larger than the covering time of the $n-1 \times n-1$ grid. A random walk on the squares is what it sounds like: from the current square choose one of its neighbors at random. Then choose the last $k$ (distinct) squares visited during the random walk. This is a simply connected region of $k$ squares: is it a uniformly random simply connected region of $k$ squares? | |
| May 5, 2011 at 4:41 | answer | added | bbejot | timeline score: 1 | |
| Mar 20, 2011 at 18:24 | comment | added | domotorp | @David: You just wasted two hours of my life with that link to the puzzle.. Thx! | |
| Mar 20, 2011 at 1:48 | comment | added | Yoshio Okamoto | @David: Thank you. Probably, it's time for me to learn the transfer matrix method more thoroughly. | |
| Mar 19, 2011 at 15:09 | comment | added | David Eppstein | @Yoshio: the transfer matrix method of counting cycles on grids of fixed width can easily be turned into a random generation algorithm. The reducibility in that case is to patterns that can be extended to a single cycle. | |
| Mar 19, 2011 at 13:23 | comment | added | Yoshio Okamoto | @David: As far as I understand, counting doesn't seem to yield sampling in this case since we'd need self-reducibility. Being constrained on a grid looks to be an obstacle, and we would need a counting algorithm for more general problem such as the number of cycles in a plane graph. Am I right? | |
| Mar 19, 2011 at 6:33 | history | edited | David Eppstein | CC BY-SA 2.5 |
added 15 characters in body
|
| Mar 16, 2011 at 15:46 | comment | added | David Eppstein | My program is not yet capable of generating correct counts for arbitrary fixed widths fully automatically, without manual calculation of the transfer matrix, but it's only a small amtter of programming until it is. Once that happens (so that I have two different calculations that agree on the same numbers) I'll send an update to OEIS. Yes, A140517 looks right, and again I can doublecheck that once my code works more generally. | |
| Mar 16, 2011 at 14:10 | comment | added | mjqxxxx | It seems like a transfer matrix for $3 \times 3$ should be straightforward as long as you consider X-X and X-Y as different cases. In any case you've got 1,13,213,... Is oeis.org/A140517 ("Number of cycles in an $n \times n$ grid") not the right sequence? | |
| Mar 16, 2011 at 12:59 | comment | added | Peter Shor | You should send that sequence to Neil Sloane so he can put it in the OEIS. | |
| Mar 16, 2011 at 7:12 | comment | added | David Eppstein | For 2xn grids the numbers are as given in oeis.org/A059020. For 3xn I'm pretty sure they are 6,40,213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247,... (not in OEIS). I set up the transfer matrix to calculate it by hand but I compared it to a machine-generated matrix and the only entry they differed the hand one was correct and the machine one was wrong. (This should show up in the 3x3 case — the machine matrix would have allowed an octomino with a hole in the center.) | |
| Mar 16, 2011 at 1:23 | comment | added | mjqxxxx | How many simple cycles are there for $2\times n$ grids? Did you work it out for $3\times n$ as well? Your struck-out sentence, I think, still holds: there's not believed to be a simple closed form, at least not for simple lattice cycles ("self-avoiding polygons" or "closed self-avoiding walks") with a given perimeter or a given area. | |
| Mar 15, 2011 at 19:56 | history | edited | David Eppstein | CC BY-SA 2.5 |
added 80 characters in body
|
| Mar 14, 2011 at 23:36 | comment | added | David Eppstein | Oops, thanks for the correction. I calculated the numbers of cycles in 2xn grids (being careful only to count simple cycles), matched it in OEIS, and found sequences in OEIS that generalize that, but as you observe there's more than one possible generalization and the one in OEIS isn't the one I actually want. | |
| Mar 14, 2011 at 21:16 | comment | added | Colin McQuillan | The boundary of the sets counted by the OEIS sequence are not necessarily simple cycles, for example for 3x3, one of the 218 has all squares except the middle, and another four are given by further removing one corner. | |
| Mar 14, 2011 at 20:12 | history | edited | David Eppstein | CC BY-SA 2.5 |
added 471 characters in body
|
| Mar 12, 2011 at 16:41 | history | edited | Hsien-Chih Chang 張顯之 |
edited tags
|
|
| Mar 12, 2011 at 5:23 | history | tweeted | twitter.com/#!/StackCSTheory/status/46441174269046784 | ||
| Mar 12, 2011 at 4:24 | history | asked | David Eppstein | CC BY-SA 2.5 |