[math-fun] looking for a non-trivial map on earth
Let's color the map of the 48 states with four colors. Note that California has only three neighbors, and therefore no matter how we color the rest of the map California is colorable, so we postpone California and get a reduced map with the rest of the states. In the reduced map Arizona has only three neighbors and can be postponed as part of coloring the reduced map. We can continue the process of postponement until we get a completely reduced map in which each state has four or more neighbors. In the case of the US, the completely reduced map is empty. This is also true for the maps of Europe and Asia, Africa, South America, and the departments of France. It is easy to construct a map in which every country has four or more neighbors. Indeed, as Kempe proved, there are maps in which every country has five or more neighbors. However, I haven't been able to find a map on the face of the earth in which every country has four or more neighbors. Can anyone find one? I'd be disappointed if the result was achieved with the aid of a disconnected country. The phenomenon can be generalized to the notion of a postponable variable in a constraint satisfaction problem. I discuss postponing countries with four or fewer neighbors in a 1982 paper entitle "Map coloring and the Kowalski doctrine". It's in my 1990 book "Formalizing common sense" and on my web site as http://www-formal.stanford.edu/jmc/coloring.html. I see no reason why our ancestors should have arranged their countries, states, provinces, and counties in such an easy to color way.
At 02:55 AM 12/25/03 -0800, you wrote:
In the case of the US, the completely reduced map is empty. This is also true for the maps of Europe and Asia, Africa, South America, and the departments of France. It is easy to construct a map in which every country has four or more neighbors. Indeed, as Kempe proved, there are maps in which every country has five or more neighbors.
My intuition is that smallish not-completely-reducible maps are rare in some sense, though in all the senses I can think of the probability of complete reducibility declines, eventually to zero, for maps with enough regions. Computer experiment would probably be instructive. Proposed experiment 1: Voronoi maps Sprinkle N points randomly on a rectangular continent. Construct the map in which each chosen point is the capital of a region; each point belongs to the region with the nearest capital. Check to see if the resulting map is completely reducible. Repeat many times and collect statistics on the prevalence of complete reducibility for different values of N. Proposed experiment 2: Census of reducibility of planar graphs Enumerate all connected planar graphs on N vertices and record whether each is completely reducible. Construct a table, being careful to keep Neil Sloane in the loop, because new sequences are bound to arise. Different criteria for when two graphs are different might alter the statistics and produce different sequences. -A
On Thu, 25 Dec 2003, John McCarthy wrote:
However, I haven't been able to find a map on the face of the earth in which every country has four or more neighbors.
If you're willing to color the ocean on your map also, then South America provides an example. In fact, it provides the minimal possible (planar) one, equivalent to the adjacency of the faces of a cube. Bolivia is surrounded by a ring of four neighbors, Peru-Chile-Argentina-Brazil and back to Peru, in which each touches the two around it. And every one of those neighbors touches the ocean. Bolivia has a fifth neighbor, Paraguay, which is postponable, but fortunately doesn't get in the way of Argentina and Brazil bordering each other. And better yet, these four contries each touch the other three, so the same region of the world also contains a minimal instance showing that four colors are necessary.
I'd be disappointed if the result was achieved with the aid of a disconnected country.
(As far as I know, there are four K_4's in the globe -- the above, another straightforward one in each of Europe and Africa, and one tricky one which does indeed use a disconnected country.)
I see no reason why our ancestors should have arranged their countries, states, provinces, and counties in such an easy to color way.
The things you're trying to color are small enough that you're coloring a map on the plane (and not, say, making use of the fact that it's on a sphere). A finite map in the plane where each region touches at least four neighbors seems to force relatively large regions around the outside boundary, compared to the inner regions -- another version of the cube, for example, looks like (bad ascii-art ahead): EEE DDDEEEE DDDaaEEE DDDaaccEE DDDbbccFF DDDbbFFF DDDFFFF FFF With nearby regions close to the same size, it's hard to deal with outside corners. (Which is why I thought using the ocean could help.) --Michael Kleber kleber@brandeis.edu PS:
Indeed, as Kempe proved, there are maps in which every country has five or more neighbors.
The dodecahedron is older than Kempe...
participants (3)
-
Allan C. Wechsler -
John McCarthy -
Michael Kleber