Re: [math-fun] Restaurant placemat mazes
Allan Wechsler <acwacw@gmail.com> wrote:
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.
Thanks. Wikipedia led me, indirectly, to https://arxiv.org/pdf/math/0410359.pdf which says: The problem of investigating pH in a variety of contexts was posed by Broadbent and Hammersley [7] in 1957. Hammersley [11, 12, 13] proved general results implying in particular that 0.35 < pH(Z2) < 0.65. The first major progress was due to Harris [14], who proved in 1960 that pH(Z2) >= 1/2. His proof makes use of the "self-duality" of Z^2, and is highly non-trivial. For many years it was believed that pH = 1/2 for bond percolation in Z^2; see, for example, Sykes and Essam [22]. However, it was only in 1980, twenty years after Harris proved that pH >= 1/2, that Kesten [16] proved this conjecture, following significant progress by Russo [20] and Seymour and Welsh [21]. I'm puzzled by this. I would think that knowing that it was self dual and that the odds of a solution were greater than or equal to one half would prove that the dual also has odds of a solution greater than or equal to one half. And since the dual obviously has a solution if and only if the original does not, it must follow that both are exactly equal to one half. What am I missing?
Site percolation on the square lattice isn’t self-dual since there can be “checkerboard” states where neither path is possible, and the threshold is 0.592746… > 1/2. But bond percolation on the square lattice is self-dual, and so is site percolation on the triangular lattice (see Hex). Maybe we’re not talking about the same things? Cris On Apr 13, 2019, at 8:58 AM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Allan Wechsler <acwacw@gmail.com> wrote:
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.
Thanks. Wikipedia led me, indirectly, to https://arxiv.org/pdf/math/0410359.pdf which says:
The problem of investigating pH in a variety of contexts was posed by Broadbent and Hammersley [7] in 1957. Hammersley [11, 12, 13] proved general results implying in particular that 0.35 < pH(Z2) < 0.65. The first major progress was due to Harris [14], who proved in 1960 that pH(Z2) >= 1/2. His proof makes use of the "self-duality" of Z^2, and is highly non-trivial. For many years it was believed that pH = 1/2 for bond percolation in Z^2; see, for example, Sykes and Essam [22]. However, it was only in 1980, twenty years after Harris proved that pH >= 1/2, that Kesten [16] proved this conjecture, following significant progress by Russo [20] and Seymour and Welsh [21].
I'm puzzled by this. I would think that knowing that it was self dual and that the odds of a solution were greater than or equal to one half would prove that the dual also has odds of a solution greater than or equal to one half. And since the dual obviously has a solution if and only if the original does not, it must follow that both are exactly equal to one half. What am I missing?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think we are talking about the same things! Keith is interested in the bond percolation question (relevant to random mazes, and hence topical for this thread). Here it would seem that since the bond situation _is_ self-dual, it follows immediately that the critical probability is 1/2. 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. On Sat, Apr 13, 2019 at 11:12 AM 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, and the threshold is 0.592746… > 1/2.
But bond percolation on the square lattice is self-dual, and so is site percolation on the triangular lattice (see Hex).
Maybe we’re not talking about the same things?
Cris
On Apr 13, 2019, at 8:58 AM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Allan Wechsler <acwacw@gmail.com> wrote:
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.
Thanks. Wikipedia led me, indirectly, to https://arxiv.org/pdf/math/0410359.pdf which says:
The problem of investigating pH in a variety of contexts was posed by Broadbent and Hammersley [7] in 1957. Hammersley [11, 12, 13] proved general results implying in particular that 0.35 < pH(Z2) < 0.65. The first major progress was due to Harris [14], who proved in 1960 that pH(Z2) >= 1/2. His proof makes use of the "self-duality" of Z^2, and is highly non-trivial. For many years it was believed that pH = 1/2 for bond percolation in Z^2; see, for example, Sykes and Essam [22]. However, it was only in 1980, twenty years after Harris proved that pH >= 1/2, that Kesten [16] proved this conjecture, following significant progress by Russo [20] and Seymour and Welsh [21].
I'm puzzled by this. I would think that knowing that it was self dual and that the odds of a solution were greater than or equal to one half would prove that the dual also has odds of a solution greater than or equal to one half. And since the dual obviously has a solution if and only if the original does not, it must follow that both are exactly equal to one half. What am I missing?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
Cris Moore -
Keith F. Lynch