Previous Up Next
Dutch / Nederlands

Diary, December 2013



Sun Mon Tue Wed Thu Fri Sat
  1   2   3   4   5   6   7
  8   9  10  11  12  13  14
 15  16  17  18  19  20  21
 22  23  24  25  26  27  28
 29  30  31


Sunday, December 1, 2013

Reductions

In the past week, I have found some more reductions with respect to the Four colour theorem. With reductions, I mean constructs that can be removed without affecting the colourability. Any closed chain of faces with six sides that touch on oppositing sides can be removed such that the corners not touching the other faces with six sides are connected. Also open chains that have end on both sides with a face with four sides can be removed. Actually, this is quite obvious, because if one the faces with four sides is removed, another faces with four sides appeares. And this process can be repeated until no square is left. Also two touching chains of three faces with five sides can be removed, leaving some connections. The same is true for two chains of five such faces. With this a dodecahedron graph can be reduced to three unconnected rings, for which can be coloured with only two colours. Also a chain of ten sides alternating connecting a side on the inside and the outside can be removed, by alternating removing and keeping a side, which can be done in two ways. Again, if this is applied to a dodecahedron graph, it results in five faces with four sides and two faces with five sides, which can be furthur reduced. I am looking into the properties of side chains with different lenghts.


Monday, December 2, 2013

Euler characteristic

With the help of the Euler characteristic for planar graphs and some other properties, it is possible to derive a statement on the number of faces with a certain number of edges. If we define Ni as the number of faces with i edges, and only faces with five or more edges are allowed, than we can write down the following equaltion:

Note that the number of faces with six sides does not appear in this equation. The equation shows that the number of faces with five sides is always larger than the number of any other kind of faces, except for the number of faces with six sides, which can be any number. However, with the constrains I mentioned yesterday with respect to the Four colour theorem, it seems hard to construct planar graphs that meet the requirements taking into account the above equation. I have not been able to construct a planar graph yet, although I have to admit that I did not try very hard yet.

plantri

I came across the paper Construction of planar triangulations with minimum degree 5 by G. Brinkmann and B. D. McKay. Through this I also found the program plantri for the generation of all kinds of triangular graphs, amongh those with minimum degree 5. This evening, I wrote a program to read the output of the program and check it for patterns that can be reduced, hoping that many graphs would contain patterns that can be reduced. However, I the only planar graph on 15 vertices already contained a pattern that could not be reduced. But it does contain an interesting kind of chain which alternates a face with six sides and a pair of faces with five sides. Maybe it can be reduced in some manner.


Wednesday, December 4, 2013

Hexagon and double pentagon chain

Yes, it is indeed possible to reduce the chain which alternating a face with six sides (a pentagon) and a pair of faces with fives sides (double pentagon). It took me some puzzling and programming, but I did find the following table:

001020            00 00 00 21 12
202020            00 00 00 21 12
100020            00 00 00 21 12
010002   12 21 00
010101   21 00 12
010200   00 12 21
112221            21 21 21 12 00
211122            12 12 12 00 21

The first row represent values around two faces with five sides on top of each other sharing one side. The values start from the left bottom and go round clockwise. The table shows how two of these patterns can be joined together side by side, creating a face with six sides in the middle. The numbers giving at the crossing are the values of the faces on top and on the bottom of the face with six sides. It shows that any sequence of values can be made. Furthermore it is the case (so I believe) that for any sequence that can occur in a planar graph, the chain can be made to close. It does not matter with which pattern in the first column you start. I do not have a proof for this, but for all sequences up to and including nine, it works usually in more than one way.


Friday, December 6, 2013

Doubling

I discovered that every planar graph can be 'doubled'. This is done by replacing each vertex with three faces with five sides and every side by a face with six sides. And that there is a trivial proof that the resulting graph can be coloured with four colours when the original graph can be coloured with four colours. This also means that a planar graph that is a 'doubling' graph of another graph can be reduced to that graph. It is also easy to see that each doubled graph has only faces with five or more edges. Furthermore, there are also many partly doubled graphs. The idea This can be done by replacing some of the faces with six sizes for replacing an edge, by a line sided by two lines. It is possible that when this is done, faces with less than five sides are created. The algorithm to check if a given planar graph is a partial 'doubling', is not very simple. You have to find a set of faces with six sides and check if they can be replaced by edges and that all those edges can be made to match. I am still seeing if there is maybe some simple reduction rule to derive from this, that would be easier to check.


Sunday, December 8, 2013

Partial doubling

My ideas about partial 'doubling' is incorrect. I also discovered that the next planar graph with one faces with five or more sides, was not based on the form of doubling that I described, but a different kind of doubling that only works for planar graphs where the faces have a multiple of three sides. I guess, it might also work with faces with other number of sides, but I have not found a simple scheme for making it work.


Wednesday, December 11, 2013

Simplest doubling

The simplest form of 'doubling' a planar graph where all vertices have degree three (only crossings with three edges meeting) is by replacing each edge with two faces with five sides joining on one side, such that at each original vertex three faces with five sides touch, such that each pair shares a side. I tried to proof that the faces of these 'doubled' planar graphs can always be coloured with at most four colours by showing that it is possible if the original planar graph can be coloured. I did find a way (except for a limited number of exceptions) that this is possible, if I could proof that it is also possible for each side to add the number 1 and 2 to the faces (one of them to each face) such that for each face the numbers added to it add up to a multiple of three. This seemed not so hard, but I could not find a simple proof for it. Today, however, I realized that there is a much simpler proof that these 'doubled' planar graphs can be coloured with four colours. These types of graphs have two kind of faces, namely faces with five sides, and faces with an even number of sides. Lets colour all the faces with an even number of sides with one and the same colour. Now it seems possible to colour the remaining faces with the other three colours. Lets consider each group of three such faces that are touching each other pairwise. It is clear that these should have three different colours. Now when we start colouring these groups starting at one point and spread out over graph. If a group just touches one group that already has been coloured, there are four ways it can be coloured, where one of outside faces has the same colour as the already coloured face it group touches. In case a group touches two groups that already have been coloured, than the faces of these groups could have the same colour or a different colour. In case they have the same colour, there are two ways the group can be coloured, such that the outside face has the same colour as this colour. In case they have a different colour, the group can be coloured in three different ways, and each way results in a different colour on the outside. The groups can be coloured in an order such that only the last remaining group is touching three groups that already have been coloured. And here there could be a problem. Because if the touching faces of all three groups have the same colour, it is impossible to colour the last group. But there is a simple strategy to avoid this, and that is to assure that the colours of the faces on the outside around the groups that have been coloured are always pairwise different.


Saturday, December 14, 2013

Wish list

At 12:28, I bought the following two books from bookshop Polare with 50% reduction: I also handed in my Christmas wish list with five books. Next Thursday at seven in the evening, they will draw one list from the people present. I put the following five books on my list: These are all books I find interesting but just too expensive to buy.


Monday, December 16, 2013

Solid proof

Some days ago, I realized that something that I had assumed to be true, might require a solid proof. Since that moment, I have been thinking about a good and simple proof This assumption is related to some of the reasoning that I have presented here with respect to the Four colour theorem. The theorem states: This translates into: Because if such a directed graph exists, it is possible to create an ordering as described, simply by starting with the start vertex and every time add a vertex to the ordering that only has incoming edges from the vertices already included in the ordering, until the finish vertex is added. This possible because if there would be no vertex at a certain step, it would either imply the existence of a directed cycle, a vertex with only outgoing edges or a vertex with only ingoing edges.

For every finite 2-connected cubic graph and two vertices designated as start and finish vertex, the following statement is true:

Because the graph is 2-connected it would mean that if the edge is removed, it would still be connected, and thus there would exists walks from both ends to the start and finish vertex. Now if there only exist walks that have at least one vertex in common, it follows from the fact that all vertices have three edges, that these walks must also have at least one edge in common. It also follows that if this edge is removed the graph must be disconnected, otherwise there would have been another walk connecting the two parts that does not contain the said edge. This is a contradiction.

Now to transform a 2-connected cubic graph into a directed graph from the start to finish vertex, begin to label the edges from the start vertex and the edges to the finish vertex into the correct direction. Now if there are still edges left that have not been labeled, select one such edge and find a minimal cut including this edge that cuts the graph in two parts separating the start and finish vertex. Each of the edges of the cut has a vertex with a walk from the start vertex and a vertex with a walk to the finish vertex. If this would not be the case, meaning that one of these walks does not exist, it means that it must be cut with another edge from the cut. And that edge could be added and still keep the start and finish vertex separated, meaning that the cut was not minimal. The edges of the cut can now be labeled in the direction from part with the start vertex to the part with the finish vertex. Now the process can be repeated with the two parts. A new vertex temporary vertex needs to be added to connect all the vertices that have edge that was cut. For the above proof it is not important that this vertex does not exactly have two edges, and that the graph is no longer completely cubic. If needed, this can be fixed with a cubic extension in which all edges can be labeled with a direction. In case there are only two edges in the cut, this can be done with a small graph consisting of four vertices and seven edges (inclusing those replacing the edges that were cut). If there are more than three edges in the cut, this can be done by creating a tree with vertices and edges in which the edges can be labeled with a direction with respect to the vertex that is selected as the start or finish vertex. This completes the proof, I believe.


Sunday, December 22, 2013

Two books and two DVD's

At 12:54, I bought the following two books from bookshop Polare:

At 13:10, I bought the following two DVD's from Aldi for € 6.99 each:


Tuesday, December 24, 2013

Komputerstrukturen 3 and 3a

When going through the online Rijkscollectie for items by Peter Struycken, I came across item AB15700, which contains a sketch of Komputerstrukturen 3. When I compared this with reproduction in Recente schilderijen (1970), I discovered one difference at the place where I earlier this year suspected a difference in the reproduction. Thus making the case stronger that the reproduction contains a difference.

I also came across a sketch for Komputerstrukturen 3a in the item AB15701. Analyses shows that this contains two anomalies, which could be caused by the following copying errors:

Taking this item as a starting point the reproduction in P. Struycken komputerstrukturen (1970) on page 17 contains the following changes: Taking this item as a starting point the reproduction in Recente schilderijen (1970) on page 3 contains the following change: The differences are disjoint, which support the hypothesis that both reproduction were independently created from the sketch on the item AB15701 or from the work made from this sketch. It is likely that the final work does contain the two anomalies found in all three versions. The item AB15701 does contain a note suggesting it was to be used as a basis for the Komputerstrukturen 3a work.


Monday, December 30, 2013

Wintergo

In the past three days (arriving on Friday evening), I attended Wintergo, a rather relaxed Go tournament. I played in three of the five rounds and only won one game. I did not play any other games outside the tournament. I did talk a lot with people and on Saturday afternoon I helped with preparing the dinner. Here on the right the final board position of the most interesting game. Both players captured three stones. White won with the komi. I spend some time to figure out how to implement a perspective projection for retrieving a straight image from a picture of a painting taken from the side.


Tuesday, December 31, 2013

Closing down sale

In the afternoon, I went to the last day of the closing down sale of the De Bijenkorf store in Enschede. In the book section there were only a few books left that were on sale, but those that were left were being sold for half a Euro. On 13:33, I bought a copy of Tegen het idealisme: Een biografie van Pierre Vinken by Paul Frentrop, ISBN:9789044611083, which has more than one thousand pages, and a DVD of Prometheus for € 4.99 including 50% reduction. On the first floor, I also found a nice McGregor coat for half the price.


This months interesting links


Home | November 2013 | January 2014