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