Open points and notes



Three edge coloring of bridgeless cubic planar graphs and rectangular maps

From Tait we know that the “Four color theorem” and the “three color theorem for the edges of a bridgeless cubic planar graphs” are strictly connected and that proving one will also prove the other.

Questions I’d like to verify:

  • The borders of regular maps form, by definition of regular map, a cubic planar graph. Can we also say that this kind of graph is always bridgeless? Answer: I don’t remember why I needed to verify this, but the answer is yes, since “An edge of a connected graph is a bridge iff it does not lie on any cycle.” and in my case every edge lie on a cycle (see: http://mathworld.wolfram.com/GraphBridge.html)
  • Is it possible to prove the Tait’s theorem “three color theorem for edges” directly on rectangular or circular maps?

An explanation of this method can be found here: http://www.mathpuzzle.com/4Dec2001.htm

How many different four coloring exist for a given map?

Two maps are regarded as differently colored if the same coloring cannot be obtained by swapping colors inside one of the two maps. Naturally it is intended that the two maps used the same set of four colors.

See here: are these different colorings?

I posted this question here: http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph

Circular maps and rectangular maps only from “regular” maps?

Usually for the four color theorem only regular maps are considered. This is because some characteristics of not regular maps are not important for the theorem, as for example enclaves or exclaves and so on. Another condition that is usually considered is the number of edges converging into a vertex. Normally vertexes with only three edges are studied.

But what about if we consider only the topological transformation to circular or rectangular maps, without caring about coloring?

Which kind of maps can be topologically deformed into circular maps (or rectangular)? Is it the same? Is not important?

Further maps simplification?

Can circular or rectangular maps be further simplified, for example choosing the faces from the original map in different orders?

Other representations of maps

We saw that maps can be deformed into circular maps or rectangular maps. But, how many other representation can be found to have a different point of view on the matter?

I know these:

  • Rectangular maps can be represented using graphs with all vertexes lying on the same line and edges represented as arcs (clef maps)
  • Starting from the clef representation, vertexes can be stretched to become lines and edges, that originally were arcs, can be deformed into lines (pipes maps)

Follow also this post: http://4coloring.wordpress.com/2011/04/25/four-color-theorem-representations-of-maps

F6 seams not to be part of this problem. Why?

Analyzing the equilibrium of the Euler’s identity 4F2+3F3+2F4+1F5+0F6-1F7-2F8-3F9+\char 46\char 46\char 46=12, faces and their numerosity seem to be tightly bound. But what about the F6? The equilibrium seems not to be touched by faces with 6 edges.

Why? Does F6 hide a bigger secret? Is it special for this theorem?

Swapping colors

Once the map has been four colored, any two colors on the map can be swapped. Here is the proof:

  • Decide which two colors you want to swap (example: R and G)
  • Select the first color (example: R) and change it to a new temporary color (example: R becomes Y = Yellow)
  • Select the second color and change it to the first one (example: G becomes R)
  • Change the temporary color to the second one (example: Y becomes G)

Considerations about arbitrarily pre-coloring some faces

In circular maps, the central face and ocean are adjacent faces and for this reason will have different colors. Since I can always swap any two colors of the map once colored (see “Swapping colors”), I can force the color of the central face to be Red and the color of the ocean to be Blue. In addition, there is another face that can be pre-colored with an arbitrary color. This face is one of the two faces adjoining both central face and the ocean (at the left and right of the central face), as in the following example. Pre-coloring, can also be used to speed up one of the coloring algorithms (see “Coloring algorithms”).

Ocean of a simplified map can always be an F5

It is easy to prove that the ocean of a simplified map on the plane can always be an F5. Just consider that:

  • Maps on the sphere and maps on the plane can be deformed into each other. It means that it is possible to switch between the two representation at any moment
  • Any simplified map (F2, F3 and F4 removed) always have faces with five edges (see the Euler’s identity in “Simplify the map”)
  • Starting from a map on the sphere it is possible to choose any face to become the ocean of the related map on the plane (see “Introduction to the 4CT”)

In other words: from a simplified map on the plane switch to the sphere representation, choose an F5 face, make a hole to it and switch back the representation to the map on the plane.

Simplified maps of 13 faces do not exist!

Let’s start considering the Euler’s identity for simplified maps: 1F5+0F6=12+1F7+2F8+3F9+\char 46\char 46\char 46 It is easy to see that, no matter the map we are considering, the minimum number of faces of type F5, necessary for the equilibrium of the formula, is at least 12. So, to have a map of 13 faces we need just to add another face to the count. But, what kind of face can it be? From the identity we can also understand that the only possible face is necessarily an F6. Any other face (F7, F8 or greater) would make things worst for the equilibrium of the Euler’s identity. For example if we try with an F7, the equilibrium would band on the right of the equality and we would need 13 faces of type F5 to balance it. So 13 (of type F5) + 1 (of type F7) = 14 faces in total, which is not what we are looking for. The only possible solutions is 12 faces of type F5 + 1 face of type F6 = 13 faces.

But these kind of maps do really exist? From the computer program I made it doesn’t seem possible. The mathematical proof can be verified following more or less these steps:

  • We know that all possible simplified maps of 13 faces have necessarily 12 faces of type F5 + 1 of type F6
  • We can start choosing one of the F5 faces adjacent to the F6
  • We can make the chosen F5 to be the ocean: from plane to sphere + hole the chosen F5 + back to plane
  • At this point, considering the ocean and the F6, what we know for sure that the map appears as in picture (A)
  • Since all the 11 internal faces (13 faces minus the ocean minus the F6) have to be of type F5, I have to check if such map exists. Luckily this can be done trying all possible combination manually
    • Lets start excluding some possibilities as shown in picture (B)
      • Can areas A and E be the same face? In this case that face would necessarily be at least an F6 (counting the existing edges), which is impossible for this simplified map, that already have an F6 in place
      • Can areas A and C be the same face? In this case area B would be an F2
      • Can A and D be the same face? In this case area B and C cannot reach 5 edges
  • At this point, what we know for sure that the map appears as in picture (C)
  • … the theorem proceed on the same path, following the pictures form E to L
    • Red lines represent attempts. Green lines represent real edges forced by logic
  • At the last picture (L), it is quite easy to see that is impossible to have all faces of type F5, proving this theorem
A B
C D
E G
H I
L M

Coloring algorithms

A coloring algorithm, if found, may suggest the way to prove the theorem. I found these methods:

  • Iterative method
    • For each face prepare a palette with four colors (“R, G, B, W”)
    • Loop all faces in sequence starting from the central face
      • Pick an unused color from the palette and mark it as used for the current face
      • Check if the partial map is correctly four colored (check previous neighbors of the current face + … other shortcuts)
      • If correctly colored move to the next face
      • If not correctly colored try another unused color and if all colors have been used, reset the palette and move back one face
    • If all faces have been looped, the map should be correctly four colored
  • Iterative method with pre-coloring of three faces: central + ocean + one facing the ocean adjacent to both
    • Considering that some faces can be arbitrarily pre-colored, I can start the coloring sequence from the second face and also avoid to try the color used by the ocean for all faces adjacent to it
  • Iterative method with pre-coloring (5 possible combinations) of all faces facing an F5 ocean
    • Considering that the ocean can always be an F5 (see “Ocean of a simplified map can always be an F5”) and that can always be colored with Blue and central face with Red (see “Considerations about arbitrarily pre-coloring some faces”), all faces facing the ocean are forced to use the three remaining colors
      • The 3 colors RGW distributed on 5 positions give some possible combinations. For convenience it is possible to start from the central Red face and proceed clockwise with the second position occupied by Green. Note that first and last position are related to adjacent faces (circular maps) and also that these combinations need to respect the coloring rules for neighbors. Given these restrictions, all possible combinations are:
        • RGRGW
        • RGRWG
        • RGWRG
        • RGWRW
        • RGWGW

Clusters of F5 (DEAD END)

If you simplify maps by removing all faces with less than five edges, to balance the Euler identity: F5+0F6=12+1F7+2F8+3F9+\char 46\char 46\char 46, many F5 have to exist respect to all other type of faces and they need to be grouped in clusters. The problem is that I am not sure if these clusters really exist. Faces may be mixed with faces of type F6 (which do not alter the Euler identity) or with faces of type >= F7. One basic counter example is showed at the end of this paragraph.

Algorithm:

  • All maps can be simplified by removing all faces with less than five edges, without affecting the search and the validity of the proof
  • Maps with only F5 and more, always have F5 in clusters: meaning F5 that are surrounded only by other F5
  • loop (until there are clusters of F5 in the map)
    • Remove the central F5 of F5 clusters (Note: So far I did not find any way to prove the coloring of these graphs)
  • Maps without F5 clusters and without F2, F3 or F4, have very few faces and, for this reason, are easily four colorable

Notes:

  • Clusters may actually be formed by F5 and F6 (see the Euler’s identity). It should be considered
  • This picture shows the graph of a map containing F5 surrounded by five other F5

DEAD END: This is a counterexample of a map (you can also add as many F5 as you want) that does not have clusters of F5.

Do F6 faces always exist in simplified maps? (DEAD END)

In simplified maps (with only F5 and greater), do F6 faces always exist?

For maps with 12 faces I found a case with only F5 faces (Euler’s equation: 12 = F5). But what about maps with 13 faces or more?

DEAD END: See the last picture of the “Clusters of F5” paragraph for a counterexample of a simplified map that does not have F6

Regularized maps and layering properties

We have seen that circular and rectangular maps can be constructed adding faces to partial maps one after the other, as you would do with a jigsaw puzzle. There is an interesting fact that should be analyzed.

Let’s say for example that the partial map we are building has 5 faces already in place and that these 5 faces are still reachable from outside the partial map.

If the new face we are adding touches many other existing faces (more than two), some of the touched edges will be completely covered and will no longer be reachable from outside. In other words, for example, if at a concentric circle of a partial map there are 50 edges still reachable and the new face touches all 50 edges (the first one and the last one not completely), at the new concentric circle (partial map + 1 face), we will have only 3 edges facing the ocean of the new partial map.

What can be noticed is that there is a relation between the complexity (number of edges) of a face at certain concentric circle and the complexity of the new map containing a new face. In non mathematical language it seams that if the new face touches a lot of edges the new partial map gets simplified and coloring resets.

Is it possible to elaborate this intuition with the help of mathematical tools to find a solution of the 4CT problem? Is there the possibility to iterate this reasoning for any additional face to get as result some magical number … as for example four ;-)?

Relation about maps and graphs

How can the following map be represented using graphs? How many edges do I have to draw between the faces named 1 and 3?

To prove the problem of coloring maps, it is adequate to consider planar graph that are simple, connected, without loops. But why exclude multiple edges? (Wikipedia: “In graph theory, multiple edges also called parallel edges or a multi-edge, are two or more edges that are incident to the same two vertexes. A simple graph has no multiple edges.”). If you need to use graphs to visualize the process of building maps (adding faces to previous sub-maps), it may be better to consider graphs with multiple edges (still without loops and all the rest). For example, considering the graph in the picture, without multiple edges, you would have not noticed that the face number 2 is actually unreachable if you want to add a face to this map. In other words: if two faces of a map have 2 edges in common, the vertexes of the related graph have to be connected with one or two edges? It does not count when coloring graphs but it is important when adding vertexes to an existing graph.

Counting maps (welcome to the room of mirrors) (TBF)

How many topologically different regular maps can be created with a given number of faces? Two maps are regarded as topologically equivalent if these can be deformed (following topological deformation rules) into each other.

A long time after I started analyzing the four color problem, I found a formula which I believed to be the right one to count regular maps and which I liked it. It was not compact and after a while I realized it wasn’t correct either. The problem I saw is that there were many duplications in it due to mirroring (symmetry). Anyway, the formula I found is:

2\sum_{x_{n}=2n+1}^{x_{n+1}}\char 46\char 46\char 46\,\sum_{x_{3}=7}^{x_{4}}\,\sum_{x_{2}=5}^{x_{3}}\,\sum_{x_{1}=3}^{x_{2}}x_{1}(x_{1}-1)(x_{2}-3)(x_{3}-5)\char 46\char 46\char 46(x_{n}-(2n-1))

Expected results:

  • 2 faces
    • There is only one possible regular map consisting of an island and the ocean surrounding the island
  • 3 faces
    • There is only one possible regular map consisting of an island split in two (there is only one regular way to split an island) and the ocean surrounding the island
  • 4 faces
    • There are three possible regular maps
  • 5 faces
    • ???

Can someone help me out with this computation?

I posted this question here: http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-created-with-n-faces

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s