The interesting thread of comments on Wednesday’s post about “electoral hex” led me to look more closely at the graph for the Lower 48 states:
I’ve constructed the graph—and it wasn’t easy, by the way—on the rule that two states are linked by an edge if they share a common boundary of more than one point. National boundaries are determined in the same way. Nodes half-shaded orange are east coast or west coast states; those half-shaded blue are north coast or south coast states. Underwater boundaries count in this scheme. Thus, for example, Illinois is adjacent to Michigan because there’s a section of boundary line between them in the middle of Lake Michigan. Similarly, Wisconsin is not a north coast state, even though it abuts Lake Superior, because it has no shared boundary with Canada.
Some properties of the graph:
- It has 48 vertices (no surprise!), 107 edges, and 60 faces (excluding the outer, embedding, face).
- It’s a planar graph (again no surprise).
- All but one of the faces are triangles. The exception is a quadrilateral formed by the Four Corners states.
- The degree sequence runs: 8 8 7 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 1. (The two octopus states are Missouri and Tennessee. The singleton is Maine.)
- The diameter is 11, and the characteristic path length (the length of the shortest path between two vertices, averaged over all pairs of vertices) is 4.1.
What about playing hex on this graph? In standard hex, one player tries to connect east to west, and the other player has to find a path from north to south. Those rules would hardly be fair with such an asymmetrical graph. So let’s adopt a modified version of the rules that I suggested for the political primaries: The players take turns, and the first to create a pathway either from north to south or from east to west is the winner. (Barry Cipra suggested that we call this the game of pox.)
Is the game a sure win for either the first or the second player (assuming correct play on both sides)? If so, what’s the right opening move?
It’s easy to find some really bad moves. As Paul Zorn noted, the New England states are not worth bothering with, because they’re sealed off by New York. But it turns out New York is not a very smart choice either. (If you take New York, I take Pennsylvania; then, if you want to get anywhere, you have to win all three of New Jersey, Delaware and Maryland, which gives me three chances to block you.)
The shortest bridging paths are along the I-5 and I-15 corridors, out west. In particular, there are five ways to construct a path of length 3 from north-to-south with the states WA, OR, CA, ID, NV, UT, AZ. But I don’t believe there’s any way a player can force a win using these states alone.
In hex, the best opening moves are generally near the middle of the board. The analogous pox strategy would choose one of the central and highly connected states such as MO, TN or KY. This seems sensible, but the games are too complicated to work out by hand.
On a regular 7 × 7 board, hex has been fully solved: The entire game tree is known for every possible opening move, so that each cell of the board is classified as a win or a loss for the first player. (This impressive feat of analysis and computation was done by R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po and J. van Rijswijck of the University of Alberta.) The Lower 48 graph is roughly the same size as the 7 × 7 hex board, so a similar method would presumably be feasible. Feasible but not easy.
Another question is whether the game can end without a winner. Jim Ward asked about this in the comments to the previous post, but I didn’t really understand the full force of the question. In the game of presidential primaries—where elections can occur simultaneously in multiple states—two or more winning paths could be created at the same time. Enforcing a strict alternating-turns policy, as I’m assuming here, eliminates that problem. But there’s another way the game might possibly fail to yield a winner, namely if all the states are chosen but there’s still no path along either axis.
In hex it’s easy to show that no such drawn game is possible. You can block the progress of a north-south path only by completing an east-west path. Hex is played on a regular and symmetrical lattice whose structure is equivalent to this graph:
The graph of the Lower 48 is not quite so uniform. The diagonals don’t all go the same way, and there’s that quadrilateral with no diagonal at the Four Corners. Does that feature (or some other oddity of the graph) allow all the states to be divided into two categories without creating either a north-south or an east-west path? I don’t think so; I haven’t been able to find such an assignment. But I’m not quite sure it can’t exist.
Update 2008-03-17: By popular request, I’ve posted a PDF version of the lower-48 graph and a text file with the vertex list and edge list. The vertex and edge lists actually take the form of a Scheme definition, but the semantics should be obvious and translation to other formats should be straightforward.
Where could one get that graph in a useful format?
Not sure what format might be useful, but see the two files I’ve just uploaded. Links are in the update at the bottom of the main post.
I thought I’d try formulating a suitable generalization of Brian’s question concerning how hard it is to tell if electoral hex could ever end in a draw. Here goes.
Let G be a graph (planar or not!), and let N, E, S, and W be 4 consecutive paths with overlapping endpoints nw, ne, se, and sw, where the notation, hopefully, is self-explanatory. The system (G,N,E,S,W) is “hex-agreeable” if for every black/white coloring of the vertices of G, there is at least one path that’s either all black or all white running either from N to S or from E to W. The problem is to decide whether a given system is hex-agreeable.
Note that by momentarily adding one more vertex attached to each of the vertices in N, E, S, and W and then drawing the augmented graph on a surface of some possibly high genus, one can interpret N,E,S,W as constituting the border states of a country on some topologically weird planet. So one can think of hex-agreeability as saying that electoral hex for this country cannot end in a draw.
It’s fairly easy to see that the Yes/No decision problem of hex-agreeability is in co-NP: If the answer is No, you can demonstrate it by giving a black/white coloring that lacks any transcontinental path. (Verifying the lack of a path is not completely trivial, but it’s clear you can do it in polynomial time.) However, it’s not clear (to me, at least) that hex-agreeability is in NP, and far from clear (again, to me) if it’s in P. Maybe some other bit-player commentator can make it clear.
To win, player 1 can play UT. Player 2 then must try to either block them to the north or to the south.
To block to the south, player 2 MUST play AZ, to which player 1 responds with CO, to which player 2 MUST respond NM, player 1 plays OK, player 2 must block with TX, and player 1 finally plays at an unblockable location, AR.
To block to the north, player 2 MUST play ID, player 1 responds with WY, and then player 2 MUST play MT. Player 1 then plays at the unblockable location, SD.
No matter how player 2 plays, player 1 can win north-to-south with an initial play of UT.