Just in case anybody doesn't know: questions like this have been studied at least since the 1950s, under the rubric of "percolation theory". The seminal work appears to be Broadbent & Hammersley 1957. See the Wikipedia article on percolation theory for the complete reference. On Wed, Apr 10, 2019 at 1:27 PM Andy Latto <andy.latto@pobox.com> wrote:
On Tue, Apr 9, 2019 at 10:34 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
It occurred to me that it's always either possible to traverse the maze west-to-east or to traverse the dual of the maze north-to-south, never both and never neither. (There can be a canal though Panama or a highway between North and South America, but not both (ignoring bridges and tunnels)). And the dual is the same size as the original maze, just with the probability of an edge being missing being changed to one minus that probability. As such, there must be a phase transition at exactly 0.5. If more than half the edges are removed, you can probably visit most of the small squares. Otherwise, you almost certainly can't.
While I think this is likely, I think more argument is needed to actually prove it. The duality argument shows that if there is a phase transition at probability p, there is also a phase transition at 1-p. But how does it show there is a phase transition at p = .5? Maybe there are two phase transitions, one at .37 and one at .63. Maybe there are no phase transitions at all, and the chance that most locations are accessible increases gradually with p, with no sudden jumps.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun