Get best of the week

Rainbow Coloring Are Mathematicians' Best Friends

Recently, rainbow colors have helped carry out a new proof. And they are not the first time to be useful.



Color coding of the Latin square and its graph can tell a lot about them.

Recently, we talked about a new proof of the Ringel hypothesis . Part of the evidence was related to the use of rainbow colorings, a special way of color coding for visualizing information. However, such coloring books have been used by mathematicians for a long time to facilitate solving puzzles, and now they are trying to apply this technique to the problem associated with the previous one.

The Ringel hypothesis is a problem from the field of combinatorics related to the construction of graphs - points (vertices) connected by lines (edges). It predicts a special relationship between large graphs of a certain type with 2n + 1 vertices and proportionally smaller graphs with n + 1 vertices.

Let's start, for example, with 11 peaks. Connect each vertex with all the others to get the so-called full graph. Next, take six of the vertices available, and connect them, as we please, only so that we do not get closed loops. Thus we get the so-called "wood".


Examples of complete graphs and trees.

Ringel’s hypothesis says that copies of any tree can ideally cover, or tile, all the edges of the corresponding complete graph - just as you can tile the kitchen floor with the same tiles.



As with the kitchen floor, for success it is necessary to choose the correct location of the first tile. The three mathematicians who came up with the proof color coded the edges of the complete graph based on the distance between the vertices to find this location.



Then they tried to arrange the tree inside the complete graph so that it covered one edge of each color. Having shown that such a “rainbow” arrangement is possible in any case, they proved that the ideal tiling predicted by Ringel always works.

However, this technique of rainbow coloring has come to the rescue not the first time.

In the 18th century, Leonard Euler became interested in something like Sudoku for children. Take a square of 3x3 cells. Euler filled it so that in each row and each column there were numbers from 1 to 3, never repeating itself. This puzzle is called the Latin square . Patterns and techniques discovered by Euler and other mathematicians in studying Latin squares have a connection with many different areas of mathematics.



Then Euler wondered: is it possible to choose three cells, one from each column and each row, so that the numbers in them do not repeat? Suppose you can select a cell from the first column of the first row containing 1, a cell from the second row of the second column containing 3, and from the third row of the third column containing 2. So, we selected three cells, each of which belongs to different rows and columns, and contains its number - 1, 3, 2. This set of cells is called transversal.



Euler wanted to know whether it is possible to divide the entire 3x3 grid (or a square grid of any size) entirely into transversal sets, so that each set has one number from each row and each column. That is, in the case of a 3x3 square, I would like to hope that we can find three different transversal sets covering together all the cells of the square.

As a result, mathematicians discovered that one way to explore this issue is to turn a square into a graph. To do this, draw three vertices on the left, denoting three columns. Then we draw three vertices on the right, representing the lines. Draw the edges connecting each vertex on the right with each vertex on the left. Each edge, being a combination of a particular row and column, represents one of nine cells. For example, the edge between the upper right vertex and the upper left vertex corresponds to the cell of the first row of the first column (upper left cell of the Latin square).



Now we get out the colored pencils and encode the colors of the ribs according to what numbers of the square they denote. Suppose we color the lines denoting 1 with blue, red with 2, yellow with 3. If 1 is in the upper left cell, then the edge between the top vertices will be blue.



Let's look at the colors of the edges. Is it possible to choose three edges of each of the three colors so that they begin and end at different vertices? This set is called rainbow matching. If you find it, it becomes clear that in the corresponding Latin square there is a transversal. Moreover, if you find three different rainbow correspondences, it becomes clear that the entire Latin square consists of transversals.



Rainbow coloring helped researchers study problems in the past, and also became a key element in the new proof of Ringel's hypothesis. They also play a role in an even more complex task, the graceful markup hypothesis .

To understand the essence of the problem, first draw six vertices, and then connect them to form a tree. Assign each vertex a number in any way. Then mark each edge with the difference between the numbers of the vertices it connects. That is, for example, if an edge connects the vertices 6 and 2, then we mark this edge with the number 4.

Your goal is to make the edge labels go in sequence and their numbers do not repeat. In this case, 1, 2, 3, 4, 5. If you can do this, then graceful markup will exist for your tree.



In the 1960s, Gerhard Ringel - the one that put forward the hypothesis - and Anton Kotsig, together suggested that any tree, regardless of the number of edges or shape, can be marked gracefully.

The graceful markup hypothesis implies the Ringel hypothesis - that is, if the first hypothesis is true, then the Ringel hypothesis is also true. To understand this, let us return to a gracefully marked tree of six vertices and a complete graph of 11 vertices. We distribute these 11 vertices around the circumference and number them from 1 to 11. Now we will place a copy of the tree on the full graph so that the labels of the vertices coincide: the vertex 5 of the tree overlaps the vertex 5 of the full graph, and so on. This placement is a rainbow copy of a gracefully marked tree.



So if you know that trees with the number of vertices n + 1 can always be gracefully marked, then you know that they can always be placed inside the corresponding complete graph with 2n + 1 vertices so as to get a rainbow copy of the tree. And such a placement will be exactly the position with which to begin the process of tiling Ringel.

“If you find graceful markup, I can tell you how to find your rainbow copy,” said Benny Sudakov of the Swiss Federal Institute of Technology, one of the three authors of the proof of the Ringel hypothesis.

Of course, mathematicians were ultimately able to prove the truth of the Ringel hypothesis without having to prove the hypothesis of graceful markup, leaving this question unanswered.

“Graceful markup is an attractive and beautiful issue in itself, and still remains open,” Sudakov said.

However, the methods that led to the proof of the Ringel hypothesis can probably be applied to graceful markup - and mathematicians are eager to find out how far these methods can lead them.

More articles:


All Articles