Category Archives: math

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

Posted on by
Reply

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.

🙂

Four color theorem: A fast algorithm

Posted on by
1

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:

Link to the full resolution image: image

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

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

Four color theorem: sage and multiple edges

Posted on by
Reply

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

Four color theorem: down to a single case!

Posted on by
Reply

This post follows directly the previous one. I’m down to a single case to prove (pag. 3).

kempe-half-cycle-swapping-method-F5-third-page-v2

I think I should move to Java coding, implementing the entire algorithm: map reduction (removing edges), color reduced map, restore of edges one at a time, adjust the coloring to the case to prove (e2 = red), apply Kc5 color switching, …, apply the half Kempe-cycle color switching.

Notes (pag. 1 and 2):

kempe-half-cycle-swapping-method-F5-first-page

Second page:

kempe-half-cycle-swapping-method-F5-second-page

Four color theorem: almost there?

Posted on by
1

Here there are some results that came out from the study of Kempe chains/cycles (of edges) in Tait coloring of a 3-regular planar graph.

Next is shown an image with a summary of the ideas behind this approach. I didn’t have the time to re-create this into computerized images. I will do it later. Soon will follow the F5 case for the part I’ve been experimenting with success (sub-condition where the two edges lies on two different Kempe-cycle – see below).

kempe-half-cycle-swapping-method

Here is the F4 case shown a little better:

kempe-half-cycle-swapping-method-F4

And here some deeper details of these ideas.

Theorem: In a well edge-colored (Tait coloring) 3-regular planar graph all Kempe chains are cycles

  • This can be easily proved showing that, once colored, the edges of any vertex use all the three colors (for example R, G, B), so if you are following the path of a Kempe chain, as for example an (G, B)-Kempe chain, the chain itself cannot end to a vertex, because one of the other two edges continues the kempe chain, unless that edge was exactly the first edge you started following the path of the chain … making it a Kempe cycle, as for example the (G, B)-Kempe cycle of this picture
  • Note: This theorem, in this form, is valid if the graph is already well colored (three colors). Consider that to say that the edges of a graph can be well colored (using three colors) is as difficult to prove as the four color theorem for the faces of a map. Never the less this result can be used to search a short proof of the four color theorem, even if it depends on the long proof ;-). Or (better) this result can be used without this dipendency on the long version, immerged in the reduction method when restoring the edges one at a time. As long as you solve the N+1 case (restore of F2, F3, F4, F5), starting from the map with only two faces (the island and the ocean surrounding it) the theorem is true
kempe-cycle

Picture-01: All Kempe-chains are Kempe-cycles

Steps and results toward a short proof of the 4ct:

  • Simplify the map removing one edge from one of the faces with 2, 3, 4 or 5 edges. Repeat this procedure until the map will have just one country left. This simplification procedure can be always done because the set { F2, F3, F4, F5 } represents an unavoidable set, so every 3-regular planar graphs has to have at least one face of the type included in the set
    • The procedure, for a simple map, is shown in the previous post: here
    • The idea is similar to the “patching” method used by Kempe, in which a “patch” with the same shape but a bit larger of a face (F2, F3, F4 or F5), was put over the face to shrink it down to a point. You can read the original paper here: On the Geographical Problem of the Four Colours
  • In reverse order, restore the edges that were removed, one at a time. Each time an edge is restore, we can face one of these conditions:
    • the edge restores an F2 – Note: particular and trivial case (see next point)
    • the edge restores an F3 – Note: trivial case
    • the edge restores an F4 – Note: Easy to handle
    • the edge restores an F5
  • F2 as a trivial case
    • When the restored edge reestablish an F2 face, it means the vertices of the resored edge, touch a single edge and so you have a spare color to use to solve this case (HAPPY END)
  • For all previous conditions (F2 can be seen as a particular case) there are two main possibile sub-conditions
    • CONDITION-1: The two edges touched by the restored edge are on a common Kempe cycle
      • If the two edges belong to a Kempe-cycle, the solution is easy. Apply a Kempe-chain color swapping to half (one of the two parts of the cycle being “cut” by the restored edge) of the cycle to solve this case (HAPPY END)
      • Consider that in case of the restored face is an F3, this is always the case, since the two edges touch each other. So also F3 can be regarded as a particular case
    • CONDITION-2: The two edges touched by the restored edge are NOT on a common Kempe cycle, but on distinct cycles … of course with no common edges
      • TBF: This is easy to handle for F4 and of course for F2 and F3 that are particular cases. For the F5 case I’m trying to prove that all cases can be reconducted to CONDITION-1

If this Example-02 the restored edge (in black) reestablish an F5 face. Both the edges (Green = on the left, Red = on the right) do non lie on the same (G-R)-cycle (CONDITION-2). Similar examples can be created when the two touched edges have the same color. In that case you can consider two different Kempe-chain ((R-x)-chain if the edges are colored Red) or you can easily reconduct that case to the one with different colors

kempe-cycle-F5-both-edges-not-on-cycles

Example-02: Example of restoring an F5

Now the diffucult part of the proof about the F5 case where the two edges do not lie on the same Kempe-cycle.

How can I reconduct a CONDITION-2 (edges NON on the same Kempe-cycle) to a CONDITION-1 (edges on the same Kempe-cycle)?

Four color theorem: back to the basics

Posted on by
1

Finally I bought two books about the four color theorem: “Four Colors Suffice: How the Map Problem Was Solved” by Robin Wilson e Ian Stewart; and the “The Four-Color Theorem: History, Topological Foundations, and Idea of Proof” by Rudolf Fritsch and Gerda Fritsch.

I am currently reading the first one, and I want to revisit the fundamentals by using the method Kempe employed when he believed he had solved the problem.

With these differences: I will approach it removing one edge at a time from F2, F3, F4, or F5 faces (unavoidable set) to reduce the map to two faces (including the ocean). Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. Instead of applying Kempe’s chain color switching solely to the faces, I will consider Tait coloring of the edges and apply Kempe’s chain color switching to the edges.

Follow the arrow to visualize the steps:

kempe-reduction-and-kempe's-chain-v3.png

Four color theorem: experimenting impasses (as in life)

Posted on by
1

I still think a solution may be found in Kempe chain color swapping … for maps without F2, F3 and F4 faces (or even without this restriction).

Or at least I want to try.

kempe-chain-impasse-v2

How you can solve the impasses (To be finished):

To explain the possible cases, without lack of generality, I can assume to start with these colors: e1=red, e2=green, e3=blue, e4=red. e4 may also be colored in green, the reasoning will not change much.

  1. If e3 and e4 are not colored … there is no impasse → OK
  2. If e3 is the same color ex should be (blu in the example) and e4 is non colored
    1. If one of the two possible chains starting from e3: (b, r)-chain or (b, g)-chain does not end at e1 or e2
      1. Use it to swap the color of e3 and solve the impasse → OK
    2. If both end at e1 or e2
      1. Try to deroute one of the two chains, using another kempe chain color swapping along the way, to fall into one the the solvable cases (2.A)
        1. If the derouted original chain does not longer end at e1 or e2, then apply the original kempe chain color swapping and solve the impasse → OK
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses
  3. If e3 is the same color ex should be, and e4 is also colored
    1. In this case the chain (…-e3–e4-…) = (b, r)-chain would simply swap the colors of e3 and e4 and therefore will not solve the impasse. It is better to use the other (b, g)-chain, starting from e3
      1. If this chain does not end at e2 (e1 is not a possible end because the chain is blue and green), use it to swap the color of e3 and solve the impasse → OK
      2. If it ends at e2
        1. Try to deroute the chain, using another kempe chain color swapping along the way, to fall into one the the solvable cases
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses

A deroute of a chain appears as in the next picture. Consider that deroutes may not work because Chain-B color swapping may change one or more of the three edges e1, e2, e4, and after appying the Chain-B swap, the chain starting with a3, may still end to one to e1, e2, e4. See this post for a real example: here.

kempe-chain-deroute-v2

About swaps of a partially colored map, I’ve asked a question on mathoverflow … here.

Maybe I was wrong when, in the motivation of the question (mathoverflow), I said that “I found many examples in which Kempe chain color swapping does not work for maps with faces of type F2, F3, F4, but I did not find an example of maps with only F5 or higher“. It seems to be possible also for maps with F2, F3, F4.

I’ll continue to search for counterexample but, for what I’ve seen so far (I tryed about 50 maps) it has been always possible to solve impasses, only proceeding by swapping colors.

This is one of the map that I thought to be a counterexample, but it is not. Its signature is:

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

impasse-in-map-not-simplified

Something else to check:

  • Since once completely colored, all chains are actually loops, when it comes to the last two impasses, if you solve one impasse also the other one gets solved!

Four color theorem: Cahit spiral chains and Tait coloring

Posted on by
Reply

I was experimenting impasses and I found this about spiral chains:

  • Consider all possible maps less than or equal to 18 faces (including the ocean)
  • Do not consider duplicates (isomophic maps)
  • There is still a very large number of possible such maps
  • Remove all maps that have faces with 2, 3, 4 edges
  • The number of maps reduces to 22 maps only
  • All these 22 maps have only one spiral chain
  • To get the Tait coloring, required me only one Kempe chain color swapping per map
  • Actually I complitely colored the spiral (the backbone) with two colors and then I finished the other edges and at the end I worked on impasses
  • Next, I’ll try the algorithm described here:

Four color theorem: counterexample to the hypothesis I was verifying :-(

Posted on by
2

Bad news … to me!

This example it is a counterexample to the hypothesis I was trying to verify!

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

😦

For this example, no Kempe color switching exists along the main chain (b-r) = (1-2-3-4-5-6-7-8) that “divert” it, to make it end at a different vertex than vx. All other chains (*-g) along the main chain (b-r) involve vx or vy.

hypothesis-counterexample-v2