Get best of the week

Rainbow proof demonstrates the presence of standard components in graphs

Mathematicians have proven that copies of smaller graphs can always ideally cover larger graphs.



On January 8, three mathematicians published a proof of a theorem from combinatorics formulated almost 60 years ago, known as the Ringel hypothesis. Roughly speaking, she predicts that graphs - constructions consisting of points and lines - can be ideally folded from identical pieces of a smaller size.

Mathematicians enthusiastically accepted the confirmation of this hypothesis.

“The good fortune is that this work solves a very old hypothesis that could not be verified by other methods,” said Gil Kalai , a mathematician at Hebrew University in Jerusalem, unrelated to this work.

Ringel’s hypothesis predicts that special types of complex graphs — with trillions of vertices and edges — can be “tiled”, i.e. completely cover, with separate copies of smaller graphs of a certain type. From a conceptual point of view, this question is similar to the following: can I completely tile the floor in the kitchen with the same copies of any tiles in the store? In real life, most types of tiles are not suitable for your kitchen - to completely cover the floor, you have to combine their different shapes. But in the world of graph theory, the hypothesis predicts that you can always tile a graph.

And in the kitchen, and in the graphs, it is important where exactly you place the first tile. The new work highlights this crucial issue - and in such a way that it is both surprising and surprisingly intuitive.

Forest with trees


In combinatorics, mathematicians study how vertices (points) and edges (lines) combine to form more complex objects called graphs. You can ask a lot of questions about graphs. One of the basic ones: in what cases are smaller and simpler graphs ideally embedded in larger and more complex ones?

“You have a set of puzzle pieces and you don’t know if you can assemble it from these pieces,” said Jacob Fox from Stanford University.

In 1963, the German mathematician Gerhard RingelHe posed a simple but broader question of this kind. Let's start, he said, with any odd number of vertices greater than 3 (for the plausibility of the hypothesis, the number of vertices must be odd, as we will see later). Connect them with edges so that each vertex connects to all the others. Then we get an object called a full graph .



Then imagine a graph of a different type. It can be a simple way - several edges connected in one line. Or a path with branching ribs. Branches can be added to other branches. You can make an arbitrarily complex graph, avoiding only closed loops. Such graphs are called trees.



Ringel's question relates to the relationship of complete graphs and trees. He said: first, imagine a complete graph of 2n + 1 vertices (an odd number). Then imagine any tree consisting of n + 1 vertices - and such trees can be very different.

Now take one of these trees and place it so that each edge of the tree coincides with the edge of the complete graph. Then we place another copy of the same tree on another part of the complete graph.

Ringel predicted that acting in this way, and starting in the right place, you could ideally bridge the entire complete graph. This means that each edge of the complete graph will be covered by the edge of the tree, and copies of the trees will not overlap.



“I can take copies of the tree. I put one copy on the full graph. She covers some ribs. Then I repeat the process. The hypothesis suggests that this can cover everything, ”said Benny Sudakov of the Swiss Federal Institute of Technology, co-author of the new evidence, together with Richard Montgomery of the University of Birmingham and Alexei Pokrovsky of the Birkbeck College at the University of London.

Finally, Ringel predicted that the graph can be tiled regardless of which of the many tree options you will use. Such a statement may seem too general. Ringel's conjecture applies to both complete graphs with 11 vertices and complete graphs with 11 trillion + 1 vertices. And the larger the complete graph, the more the number of possible trees that can be drawn for n + 1 vertices will grow. How can each of them ideally bridge the corresponding complete graph?

However, there were reasons to believe that Ringel’s hypothesis might be true. The very first confirmation was that the simplest combinatorial arithmetic did not exclude such an option: the number of edges in a complete graph with 2n + 1 vertices can always be completely divided by the number of edges in a tree with n + 1 vertices.

“The fact that the number of edges of a complete graph is divided by the number of edges of a tree is very important,” Montgomery said.

Mathematicians quickly found further evidence of the plausibility of the hypothesis, which triggered a chain of discoveries that eventually led to the proof.

Place and turn


One of the simplest trees is a star: a central peak with edges emanating from it. But it differs from the typical image of a star, because the edges do not have to be evenly distributed around the top. They all just have to come from one place, and should not intersect anywhere except the central peak. If you want to prove the correctness of the Ringel hypothesis, then a star-shaped tree will be a natural starting point.



And, of course, mathematicians quickly discovered that a star of n + 1 vertices always ideally paves a complete graph with 2n + 1 vertices. This fact is interesting in itself, but its proof made mathematicians think further.

Take a simple example. Let's start with 11 peaks. We place them in a circle and connect each vertex with all the others, obtaining a complete graph.



Now consider the star corresponding to it: the central point with five edges emanating from it.



Now we place the star so that the central vertex coincides with one of the vertices of the complete graph. We will cover several edges, but not all. Now move the star one vertex, as if turning the compass dial. We get a new copy of the star superimposed on a completely different set of edges of the complete graph.

We will rotate the star further. By the time we get back to where we started, we will pave the entire complete graph without superimposing stars - exactly as Ringel predicted.



“We know that a hypothesis cannot be discarded immediately, at least if we take a tree in the form of a star,” Sudakov said. “Moreover, we can even demonstrate this very beautifully: draw a graph on a circle, shift a star, get new copies, and replace the whole graph.”

Shortly after Ringel put forward his hypothesis, the Slovak-Canadian mathematician Anton Kotzig used this example for an even bolder prediction than that of Ringel. Ringel said that every complete graph with a 2n + 1 vertex can be tiled with any tree with an n + 1 vertex, Kotzig suggested that it can be tiled in exactly the same way as with a star: by placing the tree on a full graph and simply rotating it.

The idea seemed unrealistic. The star is symmetrical, so no matter how to place it. Most trees are crooked. They need to be placed in a very specific way in order for the rotation method to work.

“The star was a simple structure that can be placed manually, but if you have a spreading tree on your hands with a bunch of branches of different lengths, it's hard to imagine how it can be carefully placed,” said Pokrovsky.

To solve the Ringel hypothesis using the Kotsig rotary method, mathematicians needed to figure out how to place the first copy of the tree so that impassable thickets would not turn out. Fortunately, they found a colorful solution.

Rainbow coloring often makes life easier. It helps you organize a calendar or quickly distinguish one food container from another in a large family. It turns out that this can also be an effective way to figure out how to correctly place the first tree inside a complete graph.

Imagine again a complete graph with 11 vertices arranged in a circle. Mark its edges with color codes according to a simple rule that takes into account the distance between two vertices.

This distance is determined by the number of steps that must be taken to go from one vertex to another in a circle (without cutting the path inside the circle). Of course, in a circle you can always go in two directions, so we will define the distance as the shortest path between two peaks. If these are neighboring vertices, then the distance between them will be 1, not 10. If they are separated by one vertex, then the distance will be 2.



Now we color the edges of the graph according to the distance. We paint all the edges connecting the peaks located at a distance of 1 in one color - for example, blue. We paint all the edges connecting the peaks located at a distance of two units in the other - for example, yellow.

We continue to color the graph so that all the edges connecting the vertices that are at the same distance have the same color. Different distances will be encoded in different colors. For a full graph with 2n + 1 vertices, you need n colors for this. The result is a beautiful and useful picture.



Shortly after Ringel and Kotzig put forward their hypotheses, Kotzig realized that coloring his complete graph could be a guide to placing a tree on it.

The idea is to arrange the tree so that it covers one edge of each color and does not cover any color twice. Mathematicians call this arrangement a rainbow replica of a tree. Since coloring requires n colors, and a tree of n + 1 vertices will have n edges, we immediately know that with a high probability a rainbow copy can be found.



By the end of the 1960s, mathematicians understood that a rainbow copy of a tree had one special property: it denotes just the position from which you can bridge the entire graph by rotating the tree.

“If you make a rainbow copy, then everything will work,” said Pokrovsky.

After that, mathematicians already knew that they could prove the Ringel hypothesis by proving that every complete graph with 2n + 1 vertices contained a rainbow copy of any tree with n + 1 vertices. And if a rainbow copy always exists, then you can always bridge the graph.

However, to prove that something always exists is difficult. For this, mathematicians would have to show that complete graphs simply cannot but contain rainbow copies of trees. It took more than 40 years, but this is precisely what Sudakov and coauthors achieved in a new work.

Perfect packaging


Suppose you were given a complete graph with 11 vertices and a tree with six. The full graph is painted in five different colors. The tree has five edges. Your task is to find a rainbow copy of the tree inside the complete graph.

You can just put the edges of the tree on the graph in turn. The first is easy to place: you can choose any edge of any color for it. The second will be a little harder. It can lie almost anywhere except for the rib of the same color as the one just covered. And the more you place the edges of the tree, the more difficult the task becomes. Having reached the last rib, you will completely lose the choice of color - there will be only one. It remains to be hoped that you planned everything well in advance.

This idea that the task of finding a rainbow copy of a tree becomes more complicated as you place more and more edges of the tree on the graph was a necessary part of the method that three mathematicians used to solve this problem. They looked for ways to keep as much flexibility as possible towards the end of the process.

From the very beginning they knew that rainbow copies of very simple trees would be easy to find - trees that looked like a long path, without branches or with a small number of them. The most difficult thing was to correctly place the trees with many edges converging at one point - like stars, only with a more uneven and irregular shape. To place them is like pushing a stroller into a half-filled trunk of a car.

“The difficulty starts when you try to fill a complete graph with such awkward things that look like stars,” Pokrovsky said.

Anyone who fills the trunk knows that you always need to start with the most complex objects - large suitcases and large inflexible things, such as bicycles. Jackets can then always be shoved. And mathematicians have adopted this philosophy.

Imagine a tree with 11 edges. Six of them converge at a central point. Almost all the others form a single form, distant from the main one.



The hardest part to place is that part of the tree that consists of a peak with six edges. Therefore, mathematicians separated it from the rest of the tree and placed it first, so as to attach this part later - as if you decided to take apart the bed before dragging it to the second floor, and then reassembling it in the desired room. They did not even place this part of the star in the graph once - they found various places suitable for placing its copies inside the complete graph.

And then they randomly selected one copy. By doing so, they guaranteed that the remaining free space in the graph was also random - that is, with an approximately equal distribution of edges of different colors. It was in this place that they needed to place the rest of the tree - the path that they first laid aside.

They faced restrictions when choosing options for its placement. The path should be connected to the star - that part of the tree that they have already placed, and also had to cover colors that were not previously covered by the star with which it connects.

But mathematicians have left options for themselves. They could connect the path with almost any of the various copies of the star. What's even better, since the space around the star was random, they had options for choosing different colors to cover with the rest of the tree.

“Towards the very end of building trees, when the situation becomes complicated, I have not one mandatory color left, but a small choice,” Montgomery said.

Three mathematicians complete their proof with an argument from probability theory. They showed that after embedding the most complex parts of the trees, provided that the space remaining in the full column was essentially random, it would always be possible to find a way to build in the rest of the trees in order to get a rainbow copy.

“Now you can force what you put off from the very beginning, as if to soak up what is left of the tree and get a full rainbow coloring,” said Noga Alon from Princeton University.

Mathematicians have not described the exact way to find a rainbow copy for each tree with n + 1 vertices in each complete graph with 2n + 1 vertices. However, they proved that a rainbow copy must be in it.

And if a rainbow copy always exists, then you can always bridge the graph with the method predicted by Ringel. Thus, his hypothesis is true.

The proof also provides new tools for solving similar unsolved problems in combinatorics - for example, the problem of “graceful markup”, which predicts that a complete graph can be tiled even under more stringent conditions, according to which the trees need to be placed even more accurately.

“It shows that the methods that people have been thinking about for a long time really have great potential,” Fox said. “If you apply them correctly, you can solve problems that previously seemed impregnable.”

More articles:


All Articles