Four color theorem: new ideas


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
Posted in math | Tagged , | Leave a comment

Four color theorem: what next?


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, some 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 …

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

haken-appel-hardest-case-map

Posted in math | Tagged , , , , | Leave a comment

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


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

Posted in math | Tagged , , | Leave a comment

Four color theorem: Infinite switches are not enough :-( :-(


really_bad_case-ariadne_step-5-12-7-32-6-15-10A new edge 12-7 that connects the edges 6-10 and 32-15.

With this case seems that infinite random switches throughout the entire graph do not solve the impasse, which is really really really bad.

Posted in math | Tagged , , , | Leave a comment

Four color theorem: one switch is not enough :-(


Experimenting with the Python program, I have found that if you have an F5 impasse, a single switch may not be enough to solve the impasse. It means: counterexample found.

This is a bad news, since I believed that a single switch, on an appropriate edge, could have been the key to solve the theorem.

BUT

Since a limited number of switches still work, I am going to study if two switches, on appropriate edges, may work.

🙂

Posted in math | Tagged , , , | Leave a comment

Four color theorem: A fast algorithm


I have implemented an algorithm that goes really fast coloring the edges of a planar graph.

See this video and then try it youself!

Note about the Python program: To try the Python program you need to have Sage. Follow Sage instructions to install it on your computer: http://www.sagemath.org.

The algorithm considers Tait edge coloring and the equivalency of the 3-edge-coloring (known as Tait coloring) and the 4-face-coloring (the original four color theorem for maps).

The algorithm goes like this:

  • It uses a modified Kempe reduction method: it does not shrink a face (faces <= F5) down to a point, but removes a single edge from it (from faces <= F5)
  • It uses a modified Kempe chain edge color switching: when restoring edges from the reduced graph, it will swap half of the colored Kempe loop

Note that while rebuilding a map, all Kempe chains are actually Kempe loops!!!

These are the stats:

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

Almost linear … what do you think?

The first column is the original number of vertices for the planar triangulation from which the dual graph (a cubic planar graph) is computed. The seconds reported above do not consider the time to load or create the imput graph and to compute the planar embedding. You can also upload an already planar embedded graph using the -p option.

The same problem of coloring the egdes using the Sage function edge_coloring() requires very long time. I run 15 tests, and to color random graphs with 196 vertices and 294 edges, took: 7, 73, 54, 65, 216, 142, 15, 14, 21, 73, 24, 15, 32, 72, 232 seconds, for the same case where my algorithm takes less than 1 second: 100 – 196 vertices, 294 edges.

For the F5 case which requires the adjustments, I tried the following:

  • I tried to swap colors on a local Kempe loop, starting from an edge belonging to the face to restore (local)
    • It does not always work and for particular cases the algorithm can loop forever
  • I tried to swap colors on a Kempe loop along the edges of one of the two main loops at e1 or e2 (the two edges where the edge to restore ends),
    • It does not always work and for particular cases the algorithm can loop forever
  • I tried to swap colors on random Kempe loops around the map
    • It always works (so far) and these adjustments (Kempe loop color switches) are rare

The only (!?!?!?!?) thing that needs to be proved is that random switches of colors of Kempe loops is always possible to solve any type of impasse. I mean, for now I’m dealing with random attemps, I need to understand how the Kempe loops are related to each other and then find a way to know on which one I need to swap colors.

Something I need to modify about the Python program:

  • Read planar embedded graphs as Python list of lists of tuple: [[()()][()()()][()()()]]
    • [[(1542, 1545), (1545, 1787), (1787, 1542)]
      [(1389, 1347), (1347, 1348), (1348, 1389)]
      [(466, 468), (468, 712), (712, 466)]
      [(1398, 1399), (1399, 1401), (1401, 1398)]
      [(467, 423), (423, 428), (428, 467)]
      [(1407, 1404), (1404, 1405), (1405, 1407)]
      [(1644, 1645), (1645, 1690), (1690, 1644)],…]

I am also looking for faster algorithms around:

Here is the example of a colored planar graph with 1996 vertices and 2994 edges:

test-1996-vertices-2994-edges

sage 4ct.py -r 100 -o test-196 (sage)

dot -Tpng test-196.dot -o test-196.png (graphwiz)

Posted in math | Leave a comment

Four color theorem: sage and multiple edges


Implementing, using Sagemath, the algorithm of Kempe reduction and the half Kempe chain color swithing (for Tait coloring), I need to avoid multiple edges and loops … OR I’ll not be able to use functions that need embedding, as for example faces(), is_planar() and others.

Some notes:

kempe-half-cycle-swapping-method-sage-and-multiple-edges

Posted in math | Tagged , , , , , , | Leave a comment