Category Archives: math

The globe and the four color theorem

Posted on by
Reply

The four color theorem appeared in 1852, talking about the problem of coloring real maps. Let’s examine some basic aspects of these maps in relation to the four color theorem.

A world with just water and one land with no divisions, topologically equivalent to a disk, needs only two colors to paint the land and the ocean. This is the beginning, as the Pangea on Earth long ago.

If two parties want to share this land and both want to have access to the ocean and have contiguous regions, there is only one possible configuration, and the resulting map can be represented by a planar graph with 2 vertexes and 3 edges (multiedge graph). The other solutions that have been excluded by the two restrictions: “have access to the ocean” and “contiguous regions” are not so interesting for the scope of the theorem (see previous post).

If a third party comes into play, the initial region (surrounded by the ocean) has to be split among three parties, with the same two restrictions as stated before: “have access to the ocean” and “be contiguous regions”. If we consider all possible combinations, we can also see that among them there are some that can be eliminated introducing a third rule: “all faces have to touch each other”. This third rule can be added because all the configurations in which the three faces don’t touch each other contain F2 faces and therefore (is it to be proved?) can be eliminated. It will then rest only one configuration that meet all criteria, that is the one printed at the bottom right of the previous post image.

Generate planar graphs

Posted on by
Reply

There are some methods around to create planar graphs. One of these is based on the Delaunay triangulation algorithm from which you can derive its dual, a 3 regular planar graph. Tools and libraries that I found around (sage, networkx and others), permits you to save the graph using one of common format to represent the graph itself, specifically: .dot, .graphml, .GEXF, .gpickle and others). One problem that I found is that if I save the graph I loose the planar representation of it.

Since for what I am trying to do, namely demonstrate with pencil and paper that the four color theorem has a simpler demonstration, I need to work directly with the planar representation of the graph.

I decided to implement my own method (based on edge addition to planar graphs. See “John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004.”) to generate an save the graph directly using its planar representation. Get the code here at: https://github.com/stefanutti/maps-coloring-python. The program generates random planar graphs without using graphs library and most importantly without using complex algorithms, as planar embedding or planarity testing.

Planar embedding: “A combinatorial embedding of a graph is a clockwise ordering of the neighbors of each vertex. From this information one can define the faces of the embedding”.

sage: T = graphs.TetrahedralGraph()
sage: T.faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]})
[[(0, 1), (1, 2), (2, 0)],
[(3, 2), (2, 1), (1, 3)],
[(3, 0), (0, 2), (2, 3)],
[(3, 1), (1, 0), (0, 3)]]

Edge addition can start from a basic graph of four faces (bottom right). In the third last line of this picture I added edges from a graph with 3 faces and 2 vertices (considering the ocean). But as you can deduct from the other pictures I can safely start from a graph with 4 faces and 4 vertices (bottom right).

Four color theorem: A fast algorithm – 2

Posted on by
Reply

Four color theorem: A fast algorithm

These are the OLD and NEW (last column) execution times on my new laptop:

  • 100 – 196 vertices, 294 edges = 0 seconds – 0 seconds
  • 200 – 396 vertices, 594 edges = 1 seconds – 0 seconds
  • 300 – 596 vertices, 894 edges = 4 seconds – 1 second
  • 400 – 796 vertices, 1194 edges = 6 seconds – 1 second
  • 500 – 996 vertices, 1494 edges = 8 seconds – 2 seconds
  • 600 – 1196 vertices, 1794 edges = 10 seconds – 4 seconds
  • 700 – 1396 vertices, 2094 edges = 16 seconds – 6 seconds
  • 800 – 1596 vertices, 2394 edges = 18 seconds – 7 seconds
  • 900 – 1796 vertices, 2694 edges = 22 seconds – 9 seconds
  • 1000 – 1996 vertices, 2994 edges = 26 seconds – 11 seconds

Four color theorem: about edges selection

Posted on by
Reply

For the decomposition of a graph representing a map, I’m trying to use different algorithms to select the edge to remove.

The question is:

  • When you have multiple valid choices, which is the best edge to select … if any?

Some basic rules are:

  • Avoid new F5 to be created
  • Get rid of F5 whenever is possible, selecting the edge of a face with 2, 3 or 4 edges
  • Consider to remove an edge from an F5 face only if no faces with 2, 3, 4 edges exist

Here are all possibilities. Last 2 groups (removing edges from F5 and F6) don’t have to be taken into account. I just wanted to see how it continued after the cases with faces made of 2, 3, 4 and 5 edges:

edges-selection-possibilities

Four color theorem: new ideas

Posted on by
1

This is what I want to try:

  • Select an F2, F3  or F4 preferably when it is near an F5 and remove the edge that joins the two faces
    • Analyse also the balance of the Euler’s identity when removing edges, to decide if it is better to choose other couple: F2 near the highest or other possibilities
  • Let Deepmind DQN (or Tensorflow) learn the best approach for selecting faces and remove the edges
    • Controls:
      • The selection of the face and the edge based on the characteristics of the neighbor faces
    • Scope:
      • Avoid the F5 worst case (in the rebuilding phase), when it is necessary to apply the random Kempe’s color switches to solve the impasse

The rule: avoid F5 or at least do not create them.

avoid-f5

  • Remove F2 when near F5 –> Good (will get rid of the F5 and generate an F3)
  • Remove F3 when near F5 –> Good (will get rid of the F5 and generate an F4)
  • Remove F4 when near F5 –> NOT Good (will end up with another F5)
  • Remove F5 when near F5 –> Good (will get rid of the F5 and generate an F6)

Other to avoid:

  • Remove F2 when near F7 –> NOT Good (will end up with another F5)
  • Remove F3 when near F6 –> NOT Good (will end up with another F5)
  • …

NOTE:

  • It is also important to check what appens to f3 and f4

Four color theorem: what next?

Posted on by
Reply

The algorithm I use to color graphs works pretty well … BUT:

  • Sometimes (very rarely) it gets into an infinite loop where also random Kempe color switches (around the entire graph) do NOT work. The good is, if I reprocess the same graph from the beginning (since in a part of the code I choose edges randomly), the algorithm usually works fine

So, what now?

I want to try other strategies while removing edges from the original graph, to avoid the above condition. I want to eliminate the need of random swithes.

The sequence I used so far is:

  • Select an F2 and if an F2 does not exist, select an F3 an so on: F4 and then F5. Once selected the face, I remove a random edge from it, only paying attention not to chose the edge if the resulting graph is 1-connected

I want to try:

  • Change the order of selecting the faces
    • Combinations
      • 2, 3, 4, 5 –> This is the default in the current version of the program (22/Nov/2016)
      • 3, 2, 4, 5
      • 4, 2, 3, 5
      • …
    • I want to try all possible combinations to see if … may be … if I’m really lucky, one does not require random swithes
  • Once selected the face, I want to try other strategies to select the edge to remove
    • random edge –> This is the default in the current version of the program (22/Nov/2016)
    • Among all the edges of the face, select the one that is shared with the face that has less edges respect to the other F
    • … that has more edges …

A planar cubic graphs to visualize what I wrote in this post:

haken-appel-hardest-case-map

Four color theorem: Infinite switches are not enough – Rectangular maps :-(

Posted on by
Reply

I transformed the really bad case into a rectangular map to play with the Java program and Kempe random switches.

Here is the graph with the two edges to connect:

save-graph-really-bad-case

The two edges marked with the X, have to be joined by a new edge that form a new F5 face.

To try the Java program, rebuild this graph and play with the switches, it is possible to use this string:

  • 1b+, 2b+, 3b+, 4b+, 5b+, 15b+, 14b-, 13b-, 5e-, 6b-, 12b-, 4e-, 8b-, 13e-, 6e-, 9b-, 12e-, 11b-, 3e-, 14e-, 10b-, 7b-, 2e-, 8e-, 9e-, 11e-, 7e-, 10e-, 15e+, 1e+

Next is the graph that shows how the graph has been converted:

really_bad_case-ariadne_step-5-12-7-32-6-15-10-ppt