2023-07-10 05:36:58
Graph theory is a discipline of mathematics that, for different reasons, is currently very popular. For those readers who have no idea what we are talking about, they can think of a city subway map: we have some points, which are the stations, connected by other lines, which would represent the tracks or the tunnels. When we used to arrive in a city we didn’t know, we tried to get hold of a transport map and we estimated the best route to travel in that city. Today some applications do it for us, thinking of the transport network as a graph and using minimum path algorithms. In this ABCdario of mathematics they have appeared on different occasions and I am sure that they will continue to appear, as it is an object of study in constant development.
Today they appear again due to the recent discovery of the dedekind’s ninth number, an integer consisting of 42 digits and which has been sought for more than 30 years. We are going to approach this problem and its importance proposing a challenge to the reader; Let’s think of a square balanced on one of its vertices:
The challenge is to color some vertices red so that there is never a white vertex at a higher level than there is a red one. For example, the coloring that we have described, with all the white vertices, would be a valid one. Another would be, for example, the following:
The square has dimension 2 and the number of possibilities that we have to color the square following the stated rules is given by the so-called second Dedekind number, associated with dimension 2. For those who want to try it, we anticipate that this number, in the proposed case , is 6.
Before delving into the problem that has just been solved (corresponding to the ninth dimension) we are going to see what happens with the previous cases. The Dedekind number corresponding to dimension 0 is 2: the “square” in dimension 0 would only be a point and we only have two options: we can color it red or leave it white. There are no more possibilities.
If we go to dimension 1, the equivalent of the two-dimensional square would be a segment. This can only be colored in 3 different ways, following these rules:
The dimension 2 we have already mentioned. The equivalent to the square in the three-dimensional case is the cube. This case is much more complex and I recommend that we think about it manipulating a real cube (it can be a Rubik’s cube, a dice or any cubic object). If we put it, as before, attached to the lower corner, we can appreciate 4 floors: 1 vertex below, a second level in which the vertices form an equilateral triangle, a third level formed by three other vertices, which form a triangle rotated 180o with respect to the previous one and a fourth level with a single vertex.
We have represented the first floor in pink, the second in purple, the third in blue and the fourth in black. (Actually the pink vertex would coincide with the black one, but in our representation we have moved it a bit).
We challenge the reader to find the 20 ways to color the vertices of the cube with the rules described above: if a red dot appears at a certain level, no white can appear at a higher level.
If we go from the third to the fourth dimension, the problems grow: the first thing is to get an idea of how we can represent the hypercube, which would be analogous to the cube but in dimension 4.
There are several ways to represent it and we also resort to graph theory for this: we can represent three-dimensional objects in a flat way by looking at their vertices and edges. For example, the three-dimensional cube can be represented in a flat way by means of its Schelegel diagram, which amounts to removing the top cover of the cube, leaning out and seeing what is left:
The equivalent diagram for the hypercube would be something similar to the monument to the Constitution in Madrid:
With the necessary dose of abstraction we should balance the hypercube on a corner and count the number of possible colors, which in this case are 168.
In this way we have obtained the sequence 2, 3, 6, 20, 168,… which is the one that includes the so-called Dedekind numbers since he himself defined the problem in 1897 and calculated the first 5 terms of the sequence, up to 168. The next of these numbers is 7581 and was found by Randolph Church in 1940. Six years later, in 1946, Morgan Ward discovered the next term of the sequence, 7,828,354. Almost 20 years passed before finding the Dedekind number corresponding to dimension 7, and it was again Randolph Ward who was able to find that it was 2,414,682,040,998. verification of the correctness of this value was completed 10 years later, by Joel Berman and Peter Koehler.
We observe that the number of coloring possibilities increases very rapidly: the number of coloring possibilities of the hypercube in dimension 8 is a 23-digit number. Specifically, it is number 56.130.437.228.687.557.907.788 and was found by Doug Wiedemann in 1991 using a Cray 2 computer for 5 months (remember that we talked about the use of the Cray 1 computer in the challenge to calculate decimals of pi in a previous article on this same ABCdary of mathematics).
With a supercomputer
32 years have passed since the previous milestone in this adventure of finding the Dedekind numbers. But we have managed to go one step further, since Lennart Van Hirtum and Patrick De Causmaeker got this number on March 8, although the news has just been published now, after a period of necessary verification, and it will be explained to the mathematical community. next September, in a conference on Boolean functions and its applications that will take place in Norway. His project started 3 years ago, when Van Hirtum thought that, with the Noctua supercomputer located at the University of Paderborn (Germany), he would be able to tackle this problem using a technique developed by his professor De Causmaeker. This technique made it possible to tackle in 8 minutes, using a “normal” desktop computer, the problem that in 1991 was solved over 5 months with the Cray 2 but they point out that, however, to advance in the case of dimension 9 that have been able to solve now, an ordinary computer would take hundreds or thousands of years, since the number of terms of the formula that remains grows exponentially.
The image shows the solutions to the proposed challenge Wikimedia
Be that as it may, they have found that the number 286 386 577 668 298 411 128 469 151 667 598 498 812 366 is precisely the ninth Dedekind number that has been sought for 32 years. When will we find the tenth?
ABOUT THE AUTHOR
Fernando Blasco
#Mathematicians #find #42digit #number #years #searching