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
|
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.
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:
N5 = 12 + N7 + 2.N8 + 3.N9 + ...
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.
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.
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.
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.
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.
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.
Wish list
At 12:28, I bought the following two books from bookshop Polare with 50% reduction:
- The Seducer's Diary by Søren
Kierkegard. ISBN:9780141032818 for € 1.99.
- Endlosschleife: der Berliner Mauerweg.
ISBN:9783716515822 for € 10.00.
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:
- Faust by Johann Wolfgang von Goethe.
ISBN:9783618680017.
- Small pools by Fanny Tagavi and Pere Planells.
ISBN:9780823048588.
- Die Erzählungen by Thomas Mann.
ISBN:9783100485144.
- Gek op natuurkunde by Walter Lewin.
ISBN:9789400400672.
- Past Present Peru by John Cohen.
ISBN:9783869301037.
These are all books I find interesting but just too expensive to buy.
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:
For every finite 2-connected cubic graph and two vertices designaged as start and finish vertex, there
exists an ordering of the vertices such the start vertex is the first and the
finish vertex that last and such that all the vertices in between have at least
one edge with a vertex before and one edge with a vertex after them.
This translates into:
For every finite 2-connected cubic graph and two vertices designated as start
and finish vertex, there exists at transformation into a directed graph, such
that the only vertex that only has outgoing edges is the start vertex and the
only vertex that only has ingoing edges is the finish vertex. And furthermore
there are no directed cycles in the directed graph.
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:
For every edge there exists a walk from the start vertex to the vertex on one
side of the edge and a walk from the other vertex on the edge to the finish
vertex such that the two walks do not have a vertex in common.
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.
Two books and two DVD's
At 12:54, I bought the following two books from bookshop Polare:
- Verlichting in een lege verpakking by Paul van der Sterren,
ISBN:9789077228975, for € 11.00.
- Ongebonden: een boek over verlangens, haast onzegbaar
(Unmastered: A Book On Desire, Most Difficult To Tell.) by
Katherine Angel,
ISBN:9789085424147, for € 6.99.
At 13:10, I bought the following two DVD's from Aldi for € 6.99 each:
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:
- Row 4, column 3: changed black to white or
row 4, column 4: changed black to white.
- Row 49, column 7: changed white to black,
row 50, column 7: changed white to black, or
row 50, column 8: changed white to black.
Taking this item as a starting point the reproduction in
P. Struycken komputerstrukturen
(1970) on page 17 contains the following changes:
- Row 2, column 45: changed black to white.
- Row 8, column 18: changed white to black.
- Row 10, column 39: changed black to white.
- Row 20, column 31: changed black to white.
- Row 20, column 32: changed white to black.
- Row 23, column 46: changed white to black.
- Row 29, column 43: changed white to black.
- Row 44, column 7: changed white to black.
- Row 48, column 5: changed white to black.
- Row 48, column 7: changed black to white.
Taking this item as a starting point the reproduction in
Recente schilderijen (1970)
on page 3 contains the following change:
- Row 50, column 29: changed white to black.
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.
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.
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
Monday, December 30, 2013