I write, therefore I am
With this variation on a famous statement by the philosopher Descartes, I would like to express that writing about what happens in my life is important to me.
Old Kempe proof after all?I started writing a paper, thinking that I had found a truely elagant way of proving the four colour theorem based on the ideas that I developed earlier this week. But when I biked home yesterday, I discovered that I had overlooked an important fact, which destroyed the simple proof. But then I got another idea, but after investigating it a little I discovered that it might also not work. Earlier this week, I wrote to some people, why I thought that the proof I had in mind, was different from all other 'simple' proof attempts, like the first one from Alfred Kempe, namely: that the proof used an incremental procedure, instead of fixing a problem in a steady state, and that the problem it has to fix is localized. The first is actually not true and even if the second is true, it might still be true that the proof still belongs to the same catergory of proofs that are never going to work in the sense that you encounter problem cases (no matter how few they are) that can not be resolved. The reason might be that these proofs are based on a limited representation of an 'object' that does not capture all the complexity that is needed to resolve all cases. This exercise did give me some new ideas that I feel are worth pondering about. I gained some deeper understanding of the problem, and maybe that is worth all the effort.
Resolving the detailsWhat I call Kempe chains yesterday are more often called 'Kempe chains on edges'. When I searched for that term, I found a website about the Four color theorem by Mario Stefanutti, where he talks about impasses and resolving them with swapping along Kempe chains on edges, much like what I am using. So, it seems that some of my ideas are not original. He also gives a counter example of a graph where his method does not work. There are some important difference between his method and my proof strategy.
Since I wrote the above yesterday morning, I have continued thinking about it. One important observations is that both the edges on the side of an open face with the value 0 assigned to it, must have the same edge color, lets say α, because otherwise the vertex closing the open face could be assigned a value 1 or 2. Which means that the possible Kempe chains (on edges) that are connected to this node, must be αβ and αγ chains. Another observation is that Kempe chains of a certain type cannot cross within a planar cubic graph.
Lets look at the case where there are only two Kempe chains connected to the two edges. We look to the vertices attached to the neighbour edges on both sides. It seems impossible that both of the Kempe chains pass through one of these vertices, because then one of them must end at the outside edge (which is a contradiction). It is possible that one of the Kempe chains passes through both these vertices, but there is always one Kempe chain that does not pass through both. If one of the Kempe chains passes through one of the vertices, the other Kempe chain will need to be reversed, causing this Kempe chain to be broken into two pieces, where one piece leaves through the neighbour outside edge.
Now when both Kempe chains do not pass through either of the vertices at the neighbour edges, there is a problem. Because there is a counter example, where alternating reversing the Kempe chains will result in a cycle never to resolve the issue. But there is an escape. We simply have to 'pull' one of the Kempe chains to one of the vertices. Lets say the Kempe path leaving from the edge to the right of the open face at the location towards the right neighbour is an αβ Kempe path. Now there must be some vertices along the open face between the left edge and it neighbour. The vertex closest to the neighbour edge that is included in the αβ Kempe path, must have a γ edge colour on the edge on the right. If the edge on the left has the colour α we can reverse the Kempe path βγ going through this vertex, which causes the αβ Kempe path to extend towards the neighbour edge. This process can be repeated until the vertex at the neighbour edge is included. (It is possible that during this process the other Kempe path is broken, but that would be no problem, as that would result in a faster way in three Kempe path to be connected to the two edges.) This proves that it is aways possible in a finite number of Kempe path reversals to create a sequences that has a value different than 0 at the problem location.
Proof with Kempe chains?In the past week, I have been rereading parts of the book Four Colors Suffice and thinking about Kempe chains for solving the four colour theorem. For proving the four colour theorem it is sufficient to look at all 2-connected (planar) cubic graphs that are free of digons, triangles, and squares. A partial cubic graph, is a cubic graph that has some open edges on the outside. The partial cubic graphs can be ordered by the number of vertices that they contain. Every (complete) cubic graph can be reached by 'closing' one of the partial cubic graphs with three outgoing edges, by joining these three edges. Furthermore, every partial cubic graph of size n+1 can be constructed by adding a vertex to that connects either one or two of the open edges of a partial cubic graph of size n.
Every face colouring of a partial cubic graph is related to a three colouring of the edges, say with α, β, and γ (or a, b, and c, as I used in my first entry). Around each vertex the edge colours are either labeled in a clockwise or anti-clockwise manner with respect to the alphabetical order of the letters. If we assign values 1 to all clockwise and 2 to all anti-clockwise vertices, a value of 0, 1, or 2 can be assigned to each (open and closed) face by adding the values of the vertices modulo 3. For the closed (inside) faces of a partial cubic graph these should be zero. With the open (outside) faces of a partial cubic graph a cyclic sequence can be associated. With each partial cubic graphs it is possible to assign a set of sequences based on all possible face colourings (as I descibed before). It is possible that more than one face colouring of the partial cubic graph leads to the same sequence.
If a partial cubic graph of size n+1 can be constructed by adding a vertex to a partial cubic graph of size n that is connected with one open edge, then a set of sequences can be constructed by expanding the sequences of partial cubic graph of size n. Every sequence of the partial cubic graph of size n results in two sequences of the partial cubic graph of size n+1 by either inserting a 1 or a 2 at the corresponding location and adding that value (modulo 3) to its neighbours. If a partial cubic graph of size n+1 can be constructed by adding a vertex to two open edges, the set of sequences can be constructed by contracting the sequences of the partial cubic graph of size n. For every sequence that has a value 1 or 2 at the corresponding location, that value needs to be removed and substracted (modulo 3) from its neighbours. If all sequences have a 0 at the corresponding location, it is not possible to colour the partial cubic graph of size n+1 and the four colour theorem would be disproven. If we can proof that every set of sequences of all partial planar graphs of size n have at least one value unequal to 0 at every possible location, then the four colour theorem can be proven from this. (If I am not mistaken, as I reasoned before, every (complete) cubic graph can be constructed from a sequence of partial cubic graphs in increasing size such that first n/2 expansions are made and next n/2 contractions are made.)
A kempe chain is made out of a combination of two edge colours. There are thus three kinds of Kempe chains: αβ, αγ, and βγ. For a partial graph the Kempe chains form cycles (assuming that it has a correct face colouring). This is because the three edges attaced to each vertex have three distinct edge colours (either assigned in a clockwise or anti-clockwise manner). This causes each outer edge to be connected with two other outer edges through two Kempe chains marked with different combinations of the edge colours. Now suppose that there is set of sequences for a partial cubic graph of size n, such that at some location all the sequences contain the value 0. Take one of the sequences and select one of the face colourings associated with this sequence, there must be at least one, and determine the Kempe chains for this colouring. Now the edges on the sides of the open face at which the 0 is located are either connected with two, three or four Kempe chains. In case there are four connected, then pick one, and exchange the values 1 and 2 on the Kempe chain resulting in another face colouring of the partial cubic graph, which has a sequence associated with it that has a value different than 0 at the given location. In case there are three connected, one of them must connect the two edges on the side of the open face. Now exchange the values 1 and 2 on one of the other two the Kempe chains resulting in another colouring, which has a sequence associated with a value different than 0 at the location. In case there are only two Kempe chains connected to the two edges on the side of the face, exchanging the 1 and 2 values of the vertices on either of them will result in a new face colouring, but there will still be 0 at the given location. However, because every Kempe chain in a partial cubic graph traverses a distinct subset of vertices (assuming that it does not contain a digon), it means that the two edges must now be connected to three Kempe chains. If this reasoning is correct, it proves the four colour theorem, because another flip of one of the Kempe chains not connecting the two edges, will result in a sequence with a value different from 0. Thus all cases lead to a contradiction, from which it must follow that all sets of sequences of all partial cubic graphs contain at least one value different from 0 at every location.
(Remark: during the day, I have been editing this description to improve its readability.)
BookAt 12:02:58, I bought the book De Myte van Sisyfus (Dutch translation of The Myth of Sisyphus) by Albert Camus from bookshop Broekhuis for € 7.50. I had seen this book last week at the new arrivals setion, but I could no longer find it. It appeared they had placed it under novels, while I had been looking in the philosophy section.
Cycles in transition graphI looked at non-overlapping cycles in the transition graph related to the the four colour theorem. This resulted in the following table. The first column gives the length of the cycle. The second column gives the total number of walks starting from a point to itself. A total of 665 different walks. The third column gives the number of truly distinct cycles, ignoring walking direction, starting point, and use of 1 and 2. A total of 35 cycles. Behind that the distinct cycles are given.
2: 1 1 00 3: 2 1 111 4: 6 2 0102 1212 5: 10 1 01221 6: 28 4 010101 011022 011211 012012 7: 42 2 0110121 0112212 8: 76 5 01011021 01120122 01122021 01210212 11221122 9: 84 5 010112211 010121121 011011011 011201121 112112112 10: 160 8 0101101011 0101120121 0101202021 0110110212 0110120112 0112102122 0112201122 1121122122 11: 0 0 12: 256 6 010110110211 010112201121 010120220121 011201120112 011201211021 011221121121In the list of 665 walks there are no walks that appear inside another walk. I do not know what can be done with this, but it is a fact that all possible sequences are made out of these walks, were it is possible that some shorter walks occur inside longer walks.
Six pentagonsI still on and off thinking about the Four colour theorem. I have mostly thought about the question whether the two tree graph idea could lead to a solution. Lately, I have been thinking about a way to reduce the graphs to be resolved to those that are 'round' in the sends that they are not peanut shaped. If a graph is peanut shaped, you could cut it into two 'round' graphs that touch each other. As these are smaller than the whole graph, it means you can use some induction argument. Of course, a graph could have more than one constricion, but it seems that there must always be at least one who has a 'round' graph on one side. I guess that the proof that because the two smaller parts can be coloured, the whole graph can be coloured as well, might be rather complicated. At least it made me think about some shapes again that can be reduced, and I discovered that an area that exists of one pentagon surrounded by five pentagons can be reduced to a single pentagon. I also looked at other combinations of six pentagons, and I found one, inside a hexagon, that seems not to be reducable. I had somehow hoped that every configuration of six pentagons could was reducable.
Outdoor book marketThis morning I went to the outdoor book market in Tuindorp 't Lansink in Hengelo. I went there by bike. I returned with two maps and four books. The two maps are about the design of a road between between Enschede and Hengelo that I used to get there. I bought the at 11:08 for € 6.00. At 11:30, I bought the book John Lennon: De mens, de mythe, de muziek (Dutch translation of John Lennon: The Man, the Myth, the Music) by Tim Riley, ISBN:9789026324406, for € 7.50. At 11:46, I bought the book De Ontdekking van de Hemel by Harry Mulisch, ISBN:9023435605 for € 1.00. At 12:09, I bought another two books for € 1.00, namely: Andy Warhol by Victor Bockris, ISBN:9789067661201 and Anaïs Nin: Gemaskerd, ontmaskerd by Élisabeth Barillé, ISBN:9789067661577. At home I discovered, I already owned another edition of the Bockris book.
BookAt 10:42, I bought the book Hard by Raffaëla Anderson, ISBN:9050004334, from charity shop Het Goed for € 1.50.
Cursor language constructIn the past two weeks I have been working on the implementation of cursors for the Abstract Parse Trees as used in IParse. The AbstractParseTree class implements a kind of smart pointer with access to an abstract parse tree, where parts of the trees are shared as much as possible. You only have access to the top of the tree, so in case you want to modify something deep with in the tree you have to basically recreate it from that point. To avoid this, I introduced an AbstractParseTreeCursor class. I borrowed the cursor concept from relation databases where a cursor points to a record in a table. The cursor can be used to walk through a set of records and modify the current record. It is possible that a cursor becomes invalid when the row is removed by another process. Likewise, a AbstractParseTreeCursor can be come detached when the part it is point to has been removed from the value in the AbstractParseTree that it belongs to. It took me longer than expected to implement this. I also spend some time refactoring the code from a C to C++ style. The cursors to a value are forming a tree structure and at first I was using reference counting as well, which resulted in some complex code, until I found a more elegant way to solve the problem. The code still has not been fully tested and maybe some more refactoring is required, but I am quite happy with what I have achieve so far. I am still dreaming about a programming language that has the cursor concept build into it. Modifying parts of deeply nested structures seems rather imperative, but with the cursor concept it is possible to write more functional like programs. Functional language have some nice properties. So far, functional languages have not been used in distributed systems where multiple users can modify the same value, but I think that the cursor concepts extended with a revision concept could be the way to achieve this.
UlyssesAt 11:30:12, I bougth the Dutch translation of Ulysses by James Joyce, ISBN:9789023414360, from bookshop Broekhuis second hand for € 9.95.
BooksAt 11:19, I bought the following five books from the charity shop Het Goed:
Job and EcclesiastesAt 12:55:44, I bought the book Job / Prediker (Job / Ecclesiastes) written by Pius Drijver and Pé Hawinkels from bookshop Broekhuis for € 12.95. I bought this book in the first place, because I was impressed by the translation of Ecclesiastes when I read some parts of it. This has to do with the fact that Pé Hawinkels is a poet and a translator. He worked together with Pius Drijver, a catholic monk and theologian. our magnolia, who have only half opened. Today it has been a little colder than in the past days.
Unparsing with matchingI have extended the unparse algorithm op IParse with deep matching in case there are multiple alternatives. This makes sure that every part of the abstract parse tree is unparsed (assuming that the 'same' grammar is used for parsing), but that it is possible that some parts will be unparsed differently from how they were parsed. These extensions are included in this ZIP file. our magnolia in the back garden. Not very suprising, because today the highest temperature was 6 degrees highter than in the past days.
Trip to China 2010
-- contact -- Frans
My life as a hacker
The Art of Programming
HTML to LaTeX
eXtreme Programming Hamilton cycles