Re: [math-fun] Restaurant placemat mazes
Cris Moore <moore@santafe.edu> wrote:
Site percolation on the square lattice isn?t self-dual since there can be ?checkerboard? states where neither path is possible,
I could be wrong, but I don't think that's what anyone is talking about. The square lattice, or maybe I should say grid, is like a fly screen, consisting entirely of lots of equally spaced horizontal and vertical lines. Some proportion of the segments of those horizontal lines between two consecutive vertical lines, and the same proportion of the segments of the vertical lines between two consecutive horizontal lines, are randomly removed, to create a random maze. "Checkerboard" implies that at least some of the small squares are filled in. They're all hollow. The dual of the maze consists of the remaining lines. Think of them as wires, which can conduct current from one side of the maze to the opposite side only if there's continuity, i.e. an unbroken wire path. To me it's obvious that either the empty spaces connect two opposite faces or the solid lines connect the other two faces. It's impossible for both to be true or for neither to be true.
and the threshold is 0.592746? > 1/2.
Where does that number come from? Allan Wechsler <acwacw@gmail.com> wrote:
Keith's confusion, which I share, is raised by the wording in the Bollobas & Riordan paper which he quotes upthread. It seems to Keith and me that pH = 1/2 follows instantly from self-duality, but Bollobas & Riordan say that the proof is deep and non-trivial. I know Bollobas's name -- these are no lightweights. It follows that Keith and I are missing some complication to the question.
All I can think of is that maybe what I describe above as obvious is one of those things that's very difficult to formally prove. I certainly wouldn't know how to begin to do so. It's one of those things that would seem to not need a proof. I guess that means I'll never be a real mathematician. See https://xkcd.com/2042/
Site percolation on the square lattice isn?t self-dual since there can be ?checkerboard? states where neither path is possible,
I could be wrong, but I don't think that's what anyone is talking about.
Right, sorry for my misunderstanding. I think the issue with the Bollobas and Riordan paper is this. Let R_n(p) be the probability that there is a path of occupied bonds from North to South on an n-by-n square, if each bond is occupied with probability p. Duality shows that there is such a path if and only if there is not a path of non-occupied bonds from East to West. Therefore, R_n(p) = 1-R_n(1-p) . I think the challenge is showing that there is a sharp threshold when n tends to infinity, i.e., a p_c such that R_n(p) tends to 0 if p<p_c and 1 if p>p_c. Once we know this, then duality tells us that p_c=1/2. But proving that it’s a phase transition with this zero-one phenomenon is the trick.
and the threshold is 0.592746? > 1/2.
Where does that number come from?
There are lots of ways to estimate it from Monte Carlo experiments and by extrapolating from exact computations on finite squares. Here’s a nice page: https://en.wikipedia.org/wiki/Percolation_threshold <https://en.wikipedia.org/wiki/Percolation_threshold> There are a few lattices where a local transformation gives the exact threshold. For instance, for bond percolation on the honeycomb lattice, p_c is a root of 1 + p^3 - 3 p^2 = 0 because a cool thing called the star-triangle relation can be used to jump between the honeycomb and its dual the triangular lattice. Cris
Allan Wechsler <acwacw@gmail.com> wrote:
Keith's confusion, which I share, is raised by the wording in the Bollobas & Riordan paper which he quotes upthread. It seems to Keith and me that pH = 1/2 follows instantly from self-duality, but Bollobas & Riordan say that the proof is deep and non-trivial. I know Bollobas's name -- these are no lightweights. It follows that Keith and I are missing some complication to the question.
All I can think of is that maybe what I describe above as obvious is one of those things that's very difficult to formally prove. I certainly wouldn't know how to begin to do so. It's one of those things that would seem to not need a proof. I guess that means I'll never be a real mathematician. See https://xkcd.com/2042/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Cris Moore -
Keith F. Lynch