Bollobas and Riordan's "Percolation" -- cheap at Amazon

Amazon.com is selling Bollobás and Riordan's Percolation for $40.28 (marked down from $79).

Percolation isn't a subject that I'm interested enough in to buy the book (especially since our library has it), but I have talked about percolation here before and gotten some interesting responses, so I thought there might be someone out there who'd appreciate knowing.

The Frogger crossword

Check out the New York Sun's crossword for today, September 6, 2007.

The theme of this puzzle is "FROGGER", as we're told by the entry in the center; the crossword was constructed so that you can get from a square at the bottom to a square at the top going via only squares that contain letters in the word FROGGER. A picture of the solved crossword with just the FROGGER letters is at the left.

As it turned out, I'd been absent-mindedly flipping through Percolation by Geoffrey Grimmett right before taking a break to do this crossword. One of the standard results in the theory of percolationis that if we start with an infinite grid and fill in some proportion p of the squares at random, then with probability 1 there will be an infinitely large filled cluster containing the origin when p > 1/2, and if p < 1/2 there's an infinite filled cluster containing the origin with probability 0. (Usually one talks about open and closed bonds -- the lines connecting the sites -- instead of open and closed sites, but since the square lattice is self-dual that doesn't matter.)

So it's noteworthy that this is possible here; it wouldn't be possible in a random crossword. We wouldn't be able to get "far away" from a given site using only letters that are taken from some small set. The transition isn't going to be quite so sharp in the non-infinite cases, and the standard 15-by-15 crossword isn't all that close to infinity. Furthermore, finding a long path is even less likely in a crossword than in an ordinary square lattice, because in a crossword there are some black squares.

Furthermore, percolation theory usually assumes that sites are independent; this isn't true in a crossword, because the letters in sites adjacent to each other are correlated. For example, if a given square contains a T, the letter to the right of it or below it is probably more likely to be an H than otherwise, because the pair of letters "TH" is quite common. Any serious attempt to think about percolation in crosswords -- although I can't imagine anyone would study that seriously -- would have to take this into account.

A brief explanation, What is... Percolation by Harry Kesten, was published in May 2006 in the notices of the AMS.

links for 21 August

Terence Tao writes about the theorem that Danica McKellar, of Wonder Years fame, proved; she's been in the news a lot lately because of her book Math Doesn't Suck: How to Survive Middle-School Math Without Losing Your Mind or Breaking a Nail. A large part of the mainstream media said "she even proved a theorem! and it was published!" but nobody explained what the theorem was, because it takes a few pages of exposition. But Tao does a good job with it, getting in some nice statistical mechanics on the way.
(The paper itself, "“Percolation and Gibbs states multiplicity for ferromagnetic Ashkin-Teller models on Z²” " is available at McKellar's web site; I suspect this is the only instance of a mathematical theorem on a celebrity's web site, at least for suitable definitions of "celebrity". The theorem, by the way, says that the Curie temperature and the critical temperature for site percolation are equal in the Ashkin-Teller model on the square lattice.

Scott Morrison at Secret Blogging Seminar (which is becoming less secret every day) gives us grepping the Knot Atlas, which is about the Knot Atlas. The Knot Atlas is basically Wikipedia for knots. (The Knot Atlas, by the way, has no entry called "knot" or something similar that I could find. It doesn't define knots, it only tabulates them.) A knot is not exactly what the layperson would think it is; a mathematical knot is an embedding of a circle in 3-space, so the string has no ends. (Of course, one can represent any knot tied with an actual rope as a mathematical knot by splicing the ends together.) This is a continuation of the old Knot Atlas; it's a lot easier for anyone to edit a wiki. It is simultaneously a database of knot invariants, and the post I linked to is about how to extract that data.

One of the things that has always amused me about knot theory is Lord Kelvin's theory that atoms were knots; but psuedoscience often begets science. I once worked at the Department of Alchemy.

Another such wiki is qwiki for quantum physics. I don't know of any more but they seem like they could be useful, as references to various mathematical areas built by the community that actually uses them. Wikipedia plays this role to some extent, but its main function is to be a general-purpose encyclopedia so the technical details often don't make it in.

I find myself wondering if people have used wikis (with login, of course) to write mathematical papers with collaborators. (Or even alone! Since most wiki software stores old versions of pages, you could easily throw out arguments that you didn't like, confident that if they contained some seed of truth they could be recovered later.)

At Casting Out Nines, via Vlorbik: inside facts about calculators. The big one is that nobody in the "real world" actually needs a calculator; students generally have computers now, and the student versions of Maple and Mathematica are similarly priced to graphing calculators; therefore if it makes sense for students to use any sort of calculator, it should be what's usually called a "scientific" calculator. I agree. However, I have a ten-year-old TI-83 which I know pretty well, and I generally keep it around -- for when I'll be working in a coffee shop and don't feel like taking my laptop with me, or for when my officemate is using the computer. But unquestioning faith in the calculator is a bad thing. You can also read Eric Schechter's The Most Common Errors in Undergraduate Mathematics. Would it be possible to compile an analogous list for graduate students, or research mathematicians? Or do those of us at these levels make too many different errors for this to be possible?

an interesting fact about a variant of Hex

I have long known about the game of Hex, which is played on a hexagonal lattice. The game is played on a rhombus-shaped section of a hexagonal lattice, with markers of two colors; the board is illustrated at left. One player places red markers, the other blue markers; they alternate in playing. The red player is attempting to create a chain of red hexagons extending from the top of the rhombus to the bottom (these are both shaded red in the screenshot); the blue player is simultaneously attempting to create a chain of blue hexagons from the left side to the right.

There's a nice theorem which states that a game of Hex can never end without a winner. Say you're playing red. If you have blocked off all possible horizontal chains that blue might make, you must have made your own red chain connecting the top and the bottom, and vice versa. (This isn't exactly a proof but it's the gist of any formal proof of the result.)

However, I learned recently from
Bollobas and Riordan's book Percolation that although this is true, an analogous result is not true if one were to play Hex on a square lattice. If we think of one color of hexagons as "open" and the other as "closed", then the earlier result about Hex says that in the rhombus-shaped triangular lattice of points (which is dual to the hexagonal lattice), there's either an open path from the top of the lattice to the bottom or a closed path from the left to the right.

On the square lattice, there is the question of the right way to define adjacency; are two squares which touch each other only at a corner adjacent to each other? It turns out that if we say they are (so each square has eight neighbors) then it's possible to color the squares of the board so that there's a red vertical path and a blue horizontal path. (This doesn't create a problem for a hypothetical game of Hex on a square lattice, though, because we just award the win to the player who completes their path first.) If we let each square have four neighbors, though, then ties are possible; one could have a situation where the entire board is filled in and there's no red vertical path or blue horizontal path. (An example for both of these occurs if we divide the board into four quadrants, and color the entire northeastern and southwestern quadrants red and the northwestern and southeastern quadrants blue.)

But Lemma 5.9 of Bollobas and Riordan tells us that

If we colour the squares of an n by m chessboard [blue] and [red] in an arbitrary manner, then either a rook can move from the left side ot the right passing only over [blue] squares, or a king can move from top to bottom using only [red] squares, but not both.

(I've changed the colors; Bollobas and Riordan use the more traditional black and white.)

However, there's a difference between the two cases, even so. If you color in all the hexagons in an n-by-n section of the hexagonal lattice uniformly at random -- so each is red or blue with probability 1/2, and each hexagon is independent -- then by a symmetry argument, the probability of having a red vertical path and a blue horizontal path are equal, and thus are both 1/2. This doesn't mean Hex is fair -- the first player is in fact guaranteed to win under perfect play. But in the square-lattice version of the game, I suspect the player who is allowed to consider squares which share a corner as adjacent has a very large advantage.