Timeline for Probability that a randomly filled Go board has a set of white stones connected through their von Neumann neighborhoods
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19, 2012 at 11:43 | vote | accept | Roger S. | ||
| Jun 19, 2012 at 4:18 | comment | added | Ori Gurel-Gurevich | Regarding your update: the answer is no as is evident from Will's comment. | |
| Jun 18, 2012 at 21:51 | history | edited | Roger S. | CC BY-SA 3.0 |
added 201 characters in body; edited body
|
| Jun 18, 2012 at 20:34 | comment | added | Will Sawin | Depends. You can strengthen the lower bound with a tree that covers about half the squares and is connected to every square it doesn't cover, so if those are all white then the white stones are connected. This gets up to $p^{NM/2}$. Also if everything is black then that works just as well, so $p^{NM/2}+(1-p)^{NM}$. There are certainly other not-too-difficult tricks that can tighten this further. In particular there are currently big gulfs for $p$ near $1$. | |
| Jun 18, 2012 at 20:15 | history | edited | Roger S. | CC BY-SA 3.0 |
Minor language edits.
|
| Jun 18, 2012 at 20:01 | history | edited | Roger S. | CC BY-SA 3.0 |
added 124 characters in body
|
| Jun 18, 2012 at 19:59 | comment | added | Roger S. | @Will Sawin, that's a great observation, but is this about as tight as what one can hope for without a lot of work? | |
| Jun 18, 2012 at 19:49 | comment | added | Will Sawin | One can easily bound the answer to the first question between two exponentials. If every stone is white, then every white stone is connected. Then divide the board into 3 x 3 cells. If any of those cells has a white stone surrounded by black stones, then not every white stone is connected. So it's between $p^{NM}$ and $(1-p(1-p)^4)^{NM/9}$ | |
| Jun 18, 2012 at 19:39 | answer | added | Igor Rivin | timeline score: 6 | |
| Jun 18, 2012 at 19:32 | history | asked | Roger S. | CC BY-SA 3.0 |