[math-fun] Fun with maps
I typed in a list of which US states border which other US states, so I can write programs to do various things with it. For instance by creating an adjacency matrix and raising it to successive powers, I was able to determine which states are furthest apart in the sense that you have to cross the most borders to get between them without leaving the US. (Maine to either Washington or Oregon requires at least 12 state border crossings. That's the record, unless you count the two states that can't be reached at all.) I thought I had found the record in-alphabetic-order trip, IA IL IN KY MO TN VA WV, until I realized that I was doing alphabetic order by state *abbreviation*. Oops! The longest trips by alphabetic order are shorter than that. I'll leave them to others to rediscover -- or to try longest trip by states in order of population, area, or anything else quantifiable. I only ran into trouble when attempting to verify that the list was correct. Well, not correct, necessarily, but consistent. Of course I made sure that if A borders B then B border A, and that no state borders itself. But what about impossible maps? Or, to put it in mathematical terms, a non-planar graph? This turns out to be surprisingly hard. I'm familiar with Kuratowski's theorem, but I estimate it would take at least a month of CPU time to test every possible set of 5 or 6 states. (No, applying it only to states that border each other is invalid.) And for larger maps, it would be completely infeasible. Of course I want any software I write to work with any map, not just with this map. My first thought was that the states that border a given state should always be able to be put into a circular order. If A borders B, there should always be exactly two states that border both A and B. If I start with one of them and look at states that border A and this new state, I should keep getting a succession of different states that border A, until I return to B, and there should be no bordering states unaccounted for or duplicated. For instance Tennessee (which is tied for the record of most bordering states) borders my home state of Virginia. Those two states border Kentucky. Tennessee and Kentucky both border Missouri. Tennessee and Missouri both border Arkansas. Tennessee and Arkansas both border Mississippi. Tennessee and Mississippi both border Alabama. Tennessee and Alabama both border Georgia. Tennessee and Georgia both border North Carolina. Tennessee and North Carolina both border Virginia, and we're back where we started, with no states listed as bordering Tennessee unaccounted for, nor any appearing twice. Of course we run into a problem with a state on the border of the country. But we can create a new "state," the Exterior. I also added Lake Michigan and Four Corners as "states," so that every border ends on another border. It didn't work. Sometimes the same state shows up twice when going around the border of a state. For instance Virginia borders Maryland twice, once on each side of DC. New York borders the Exterior twice. Whenever that happens, it can only be because one or more states are enclosed by state A and the twice-bordering state B. Maryland and Virginia enclose DC. New York and the Exterior enclose all the New England states. To find these enclosed states, I zero the rows and columns representing the two enclosing states from the adjacency matrix, completely delete the rows and columns representing Alaska and Hawaii, and raise the matrix to successive powers. If all the zeros (other than in the two rows and columns I zeroed) go away, then there's an inconsistency, a "tunnel" from the enclosed states to the rest of the world. Otherwise, I regard the states which have more than half of their rows as persistent zeros as being enclosed. (Since there are an even number of states, I could in principle get a tie, where exactly half the states are on one side of the "wall" created by the two states in question and exactly half are on the other. In that case every row would be exactly half zeros and I'd have to make an arbitrary choice which is inside and which is outside. I don't want to privilege the Exterior; I'd prefer to treat every state the same. Anyhow, the Exterior may be one of the two enclosing states.) (It just occured to me that in principle there could be any number of enclosures by the two states in question, and if there are enough of them they could all be very small. Sigh.) This works. But sometimes *three* states enclose a set of states. And doing the same thing with three states doesn't work. For instance it claims that Maryland, Virginia, and West Virginia surround DC, and that's not the case, as West Virginia does not border DC. I think I can make it work if I keep track of what any two of those three states enclose, and deal with that somehow. But what a pain. Anyhow, I'm not at all convinced that what I'm doing would prove consistency anyway, rather than just finding one possible failure mode. Here's my list, if anyone else wants to play with it: AK: EX AL: EX FL GA MS TN AR: LA MO MS OK TN TX AZ: CA EX FC NM NV UT CA: AZ EX NV OR CO: FC KS NE NM OK UT WY CT: EX MA NY RI DC: MD VA DE: EX MD NJ PA EX: AK AL AZ CA CT DE FL GA HI ID LA MA MD ME MI MN MS MT NC ND NH NJ NM NY OH OR PA RI SC TX VA VT WA WI FC: AZ CO NM UT FL: AL EX GA GA: AL EX FL NC SC TN HI: EX IA: IL MN MO NE SD WI ID: EX MT NV OR UT WA WY IL: IA IN KY LM MO WI IN: IL KY LM MI OH KS: CO MO NE OK KY: IL IN MO OH TN VA WV LA: AR EX MS TX LM: IL IN MI WI MA: CT EX NH NY RI VT MD: DC DE EX PA VA WV ME: EX NH MI: EX IN LM OH WI MN: EX IA ND SD WI MO: AR IA IL KS KY NE OK TN MS: AL AR EX LA TN MT: EX ID ND SD WY NC: EX GA SC TN VA ND: EX MN MT SD NE: CO IA KS MO SD WY NH: EX MA ME VT NJ: DE EX NY PA NM: AZ CO EX FC OK TX NV: AZ CA ID OR UT NY: CT EX MA NJ PA VT OH: EX IN KY MI PA WV OK: AR CO KS MO NM TX OR: CA EX ID NV WA PA: DE EX MD NJ NY OH WV RI: CT EX MA SC: EX GA NC SD: IA MN MT ND NE WY TN: AL AR GA KY MO MS NC VA TX: AR EX LA NM OK UT: AZ CO FC ID NV WY VA: DC EX KY MD NC TN WV VT: EX MA NH NY WA: EX ID OR WI: EX IA IL LM MI MN WV: KY MD OH PA VA WY: CO ID MT NE SD UT (Watch out that your mail reader doesn't break the long line "EX.") Also feel free to post other "maps" in the same format, either maps of real places or perverse maps designed to stress-test software, perhaps with hidden inconsistencies.
Keith Lynch wrote:
I typed in a list of which US states border which other US states, so I can write programs to do various things with it. ... I only ran into trouble when attempting to verify that the list was correct. Well, not correct, necessarily, but consistent. Of course I made sure that if A borders B then B border A, and that no state borders itself. But what about impossible maps? Or, to put it in mathematical terms, a non-planar graph? This turns out to be surprisingly hard. I'm familiar with Kuratowski's theorem, but I estimate it would take at least a month of CPU time to test every possible set of 5 or 6 states. (No, applying it only to states that border each other is invalid.) And for larger maps, it would be completely infeasible. Of course I want any software I write to work with any map, not just with this map.
http://en.wikipedia.org/wiki/Planarity_testing briefly describes a few efficient ways of testing for planarity. -- g
A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane. But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant. --Dan P.S. This is a version of what's called multidimensional scaling. On 2013-02-17, at 12:25 PM, Gareth McCaughan wrote:
Keith Lynch wrote:
I typed in a list of which US states border which other US states, so I can write programs to do various things with it. ... ...
But what about impossible maps? Or, to put it
in mathematical terms, a non-planar graph?
http://en.wikipedia.org/wiki/Planarity_testing briefly describes a few efficient ways of testing for planarity.
On 17/02/2013 23:41, Dan Asimov wrote:
A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane.
But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant.
Why would one do that, rather than using one of the deterministic linear-time algorithms mentioned on the Wikipedia page? -- g
Well, I'd probably try it, if compute time were not at issue, just to see what the graph, if planar, looks like when embedded in the plane. --Dan On 2013-02-17, at 4:21 PM, Gareth McCaughan wrote:
On 17/02/2013 23:41, Dan Asimov wrote:
A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane.
But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant.
Why would one do that, rather than using one of the deterministic linear-time algorithms mentioned on the Wikipedia page?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 18/02/2013 06:46, Dan Asimov wrote: [me:]
Why would one do that, rather than using one of the deterministic linear-time algorithms mentioned on the Wikipedia page?
[Dan:]
Well, I'd probably try it, if compute time were not at issue, just to see what the graph, if planar, looks like when embedded in the plane.
Several of the methods listed on that page do compute a planar embedding when there is one. (They don't do the actual *layout*; you'd still need to work out just where to put the vertices. But finding a planar layout is easy once you've got the topology, and finding a *nice* planar layout is probably best done by first finding any planar layout and then improving it.) -- g
what is the probability that a graph this size is planar? does that question even make sense? bob --- Dan Asimov wrote:
Well, I'd probably try it, if compute time were not at issue, just to see what the graph, if planar, looks like when embedded in the plane.
--Dan
On 2013-02-17, at 4:21 PM, Gareth McCaughan wrote:
On 17/02/2013 23:41, Dan Asimov wrote:
A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane.
But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant. Why would one do that, rather than using one of the deterministic linear-time algorithms mentioned on the Wikipedia page?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
With the number of vertices fixed at N, each of the N-choose-2 pairs of vertices could be considered to be an edge with probability ½ (or more generally p). --Dan On 2013-02-18, at 5:14 AM, Robert Baillie wrote:
what is the probability that a graph this size is planar? does that question even make sense?
On 18/02/2013 18:06, Dan Asimov wrote:
On 2013-02-18, at 5:14 AM, Robert Baillie wrote:
what is the probability that a graph this size is planar? does that question even make sense?
With the number of vertices fixed at N, each of the N-choose-2 pairs of vertices could be considered to be an edge with probability ½ (or more generally p).
If you use probability 1/2, the probability is very small -- planar graphs have to be very sparse. (Add enough edges to make the graph a triangulation; then Euler's formula kinda says that the average degree is about 6.) Erdos and Renyi proved that if you take a random graph with n vertices and n/2 + k n^2/3 edges, there's a nonzero probability that it's not planar. Noy, Ravelomanana and Rue found an explicit formula for the limiting probability as n->oo, as a function of k. When k=0 the probability of planarity is about 0.998. As k->oo the probability of planarity goes to 0. (So, in particular, if you take p = c/n for c>1 then the probability that the graph is planar -> 0 as n -> oo.) I am not an expert on any of this stuff; I just looked it up :-). -- g
On 02/19/2013 06:36 PM, David Wilson wrote:
So just how many 4-colorings of the U.S. map are there?
Forgive me for doubting (especially with that URL), but it looks like that's just one coloring and its 4! permutations. Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Feb 20, 2013 at 10:03 PM, John Aspinall <j@jkmfamily.org> wrote:
On 02/19/2013 06:36 PM, David Wilson wrote:
So just how many 4-colorings of the U.S. map are there?
http://fakeisthenewreal.org/**19trillion/<http://fakeisthenewreal.org/19trillion/>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
No forgiveness needed, I think you're correct. Maine, Florida, and Washington State should have around the least amount of mutual constraint, given their separation. Yet they always come up with identical colors. Too bad, I thought it was a little deeper than that. - John Aspinall On February 20, 2013 at 10:43 PM Charles Greathouse <charles.greathouse@case.edu> wrote:
Forgive me for doubting (especially with that URL), but it looks like that's just one coloring and its 4! permutations.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Feb 20, 2013 at 10:03 PM, John Aspinall <j@jkmfamily.org> wrote:
http://fakeisthenewreal.org/**19trillion/<http://fakeisthenewreal.org/19trillion/>
Yeah, and I checked the states touching Tennessee. In about 10 tries, they always represented mere color permutations of each other. --Dan On 2013-02-21, at 9:10 AM, John Aspinall wrote:
No forgiveness needed, I think you're correct. Maine, Florida, and Washington State should have around the least amount of mutual constraint, given their separation. Yet they always come up with identical colors. Too bad, I thought it was a little deeper than that.
- John Aspinall
On February 20, 2013 at 10:43 PM Charles Greathouse <charles.greathouse@case.edu> wrote:
Forgive me for doubting (especially with that URL), but it looks like that's just one coloring and its 4! permutations.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Feb 20, 2013 at 10:03 PM, John Aspinall <j@jkmfamily.org> wrote:
http://fakeisthenewreal.org/**19trillion/<http://fakeisthenewreal.org/19trillion/>
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The chromatic polynomial is probably doable. Rich ------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
How does one calculate the chromatic polynomial without knowing the number of k-colorings for k <= #(V) ? --Dan On 2013-02-20, at 11:27 PM, rcs@xmission.com wrote:
The chromatic polynomial is probably doable.
Rich
------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You can use the method of deletion and contraction (or its converse): Let F(G) be the chromatic polynomial of G. 1) if G = G1 union G2 as disjoint graphs then F(G) = F(G1) F(G2) 2) Let e be an edge of G, and let G1 be the graph that you get by deleting e, and G2 the graph you get by contracting e (i.e. identify the end points. Then F(G) = F(G1) - F(G2). Do that recursively, and cache isomorphic subgraphs. The converse way (if the graph is close to a complete graph) is to add edges. Victor On Thu, Feb 21, 2013 at 2:01 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does one calculate the chromatic polynomial without knowing the number of k-colorings for k <= #(V) ?
--Dan
On 2013-02-20, at 11:27 PM, rcs@xmission.com wrote:
The chromatic polynomial is probably doable.
Rich
------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Using the data from http://www-cs-staff.stanford.edu/~uno/contiguous-usa.dat and Maple's ChromaticPolynomial procedure I get the polynomial which is 0 for x = 1,2,3 and for x = 4 gives 25623183458304, the number of 4-colorings. On Thu, Feb 21, 2013 at 2:50 PM, Victor Miller <victorsmiller@gmail.com>wrote:
You can use the method of deletion and contraction (or its converse):
Let F(G) be the chromatic polynomial of G.
1) if G = G1 union G2 as disjoint graphs then F(G) = F(G1) F(G2) 2) Let e be an edge of G, and let G1 be the graph that you get by deleting e, and G2 the graph you get by contracting e (i.e. identify the end points. Then F(G) = F(G1) - F(G2).
Do that recursively, and cache isomorphic subgraphs.
The converse way (if the graph is close to a complete graph) is to add edges.
Victor
On Thu, Feb 21, 2013 at 2:01 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does one calculate the chromatic polynomial without knowing the number of k-colorings for k <= #(V) ?
--Dan
On 2013-02-20, at 11:27 PM, rcs@xmission.com wrote:
The chromatic polynomial is probably doable.
Rich
------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In case the chromatic polynomial does not come through here it is again in a different format. x*(x-1)^3*(x-2)^12*(x^31-74*x^30+2662*x^29-62009*x^28+1051192*x^27-13817954*x^26+146540197*x^25-1287959730*x^24+ 9563897097*x^23-60861199906*x^22+335505665807*x^21-1615450771201*x^20+6836940711775*x^19-25554817600059*x^18+ 84651979013714*x^17-249103966596626*x^16+652062513996036*x^15-1518903799875716*x^14+ 3146686741088193*x^13-5788570890576155*x^12+9430091492582543*x^11-13550867810367132*x^10+ 17082113473194601*x^9-18750992054746828*x^8+17746420485663203*x^7-14289063407025521*x^6+ 9610593113770304*x^5-5261190717302787*x^4+2255365841830048*x^3-711273204791358*x^2+146988563481064*x-14958585349094)*(x-3)^2 Maple found it in 56.7 seconds. On Thu, Feb 21, 2013 at 3:33 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
Using the data from http://www-cs-staff.stanford.edu/~uno/contiguous-usa.dat and Maple's ChromaticPolynomial procedure I get the polynomial
which is 0 for x = 1,2,3 and for x = 4 gives 25623183458304, the number of 4-colorings.
On Thu, Feb 21, 2013 at 2:50 PM, Victor Miller <victorsmiller@gmail.com>wrote:
You can use the method of deletion and contraction (or its converse):
Let F(G) be the chromatic polynomial of G.
1) if G = G1 union G2 as disjoint graphs then F(G) = F(G1) F(G2) 2) Let e be an edge of G, and let G1 be the graph that you get by deleting e, and G2 the graph you get by contracting e (i.e. identify the end points. Then F(G) = F(G1) - F(G2).
Do that recursively, and cache isomorphic subgraphs.
The converse way (if the graph is close to a complete graph) is to add edges.
Victor
On Thu, Feb 21, 2013 at 2:01 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does one calculate the chromatic polynomial without knowing the number of k-colorings for k <= #(V) ?
--Dan
On 2013-02-20, at 11:27 PM, rcs@xmission.com wrote:
The chromatic polynomial is probably doable.
Rich
------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's in Knuth, so it must be true! "Let's return to the graph of contiguous states for one more example. That graph is planar; suppose we want to color it with four colors. Since the colors can be given 2-bit codes {00, 01, 10, 11}, it's easy to express the valid colorings as a Boolean function of 98 variables that is true if and only if the color codes ab are different for each pair of adjacent states: COLOR(a_ME, b_ME, ..., a_CA,b_CA) = ... Each of the four INDs has a BDD of 854 nodes, which can be computed via (72) with a cost of about 70 kilomems. The COLOR function turns out to have only 25579 BDD nodes. Algorithm C now quickly establishes that the total number of ways to 4-color this graph is exactly 25,623,183,458,304 -- or, if we divide by 4! to remove symmetries, about 1.1 trillion." - D. E. Knuth. The Art of Computer Programming. vol 4A. Combinatorial Algorithms. 7.1.4 Binary Decision Diagrams. Page 233. On Thu, Feb 21, 2013 at 3:33 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
Using the data from http://www-cs-staff.stanford.edu/~uno/contiguous-usa.dat and Maple's ChromaticPolynomial procedure I get the polynomial
which is 0 for x = 1,2,3 and for x = 4 gives 25623183458304, the number of 4-colorings.
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
On 17 Feb 2013 at 14:39, Keith F. Lynch wrote:
My first thought was that the states that border a given state should always be able to be put into a circular order. If A borders B, there should always be exactly two states that border both A and B. If I start with one of them and look at states that border A and this new state, I should keep getting a succession of different states that border A, until I return to B, and there should be no bordering states unaccounted for or duplicated.
I'm not exactly sure but Wisconsin is a bit of a problem: it is bordered by Michigan, Illinois, Iowa, Minnesota and Exterior. But Michigan doesn't border Illinois. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
Bernie Cosell:
I'm not exactly sure but Wisconsin is a bit of a problem: it is bordered by Michigan, Illinois, Iowa, Minnesota and Exterior. But Michigan doesn't border Illinois.
Keith F. Lynch:
IL: IA IN KY LM MO WI MI: EX IN LM OH WI MN: EX IA ND SD WI WI: EX IA IL LM MI MN
We have to remember that borders go over/under bodies of water. A quick look at the map shows that Illinois borders Michigan in Lake Michigan and Minnesota borders Michigan in Lake Superior. Wisconsin does *not* border Exterior (in Lake Superior) because the Minnesota-Michigan border prevents it.
participants (13)
-
Bernie Cosell -
Charles Greathouse -
Dan Asimov -
David Wilson -
Gareth McCaughan -
Hans Havermann -
John Aspinall -
Keith F. Lynch -
rcs＠xmission.com -
Robert Baillie -
Robert Munafo -
Victor Miller -
W. Edwin Clark