Researchers almost let the solution to a math puzzle slip away

Computer science researchers from the University of Copenhagen and the Technical University of Denmark (DTU) thought they were five years away from solving a mathematical riddle from the 1980s. In reality, and without knowing it, they had almost cracked the problem and had just given much of the solution in a research article. The solution could be used to improve tomorrow’s phones and computers.

Jacob Holm and Eva Rotenberg

A real brain teaser. That is how one can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the Department of Computer Science and the University of Copenhagen of the University of Copenhagen have now solved a problem with which the fastest and smartest in the world since the 1980s have wrestled.

The two computer scientists, assistant professor Jacob Holm of UCPH and associate professor Eva Rotenberg of DTU almost gave away their solution in the summer of 2019, after submitting a research article that became the forerunner of the article in which she definitively solves the mathematical riddle .

“We had almost given up on getting the last piece and solving the riddle. We thought we had a small result, one that was interesting, but in no way solved the problem. We estimated that it would take another five years to work. would be, at best, before we could solve the puzzle, “explains Jacob Holm, who is part of BARC, the algorithm section at UCPH’s Department of Computer Science.

The three help problems

In 1913 a forerunner of the now solved mathematical conundrum was published in It Strand Magazine as “The problem with three tools”. It caused the readers of the magazine to scratch their heads and think. In the problem, each of three houses must have water, gas and electricity, while the ‘lines’ between the houses and water, electricity and gas may not cross each other – which is not possible.

A solution between the lines

Simply put, the puzzle is about how to connect a number of points in a graph without crossing the lines that connect them. And how, with a mathematical calculation – an algorithm – you can make changes in an extensive “graphing network” to ensure that no lines intersect without having to start over. Features that can be used for, among other things, the construction of immense road networks such as the small interiors of computers, whereby electrical circuits on steering stations may not cross.

Jacob Holm has been interested in the mathematical conundrum since 1998, but the answer was only revealed while the two researchers were reading through their already submitted research article. In the meantime, the researchers heard about a new mathematical technique that they realized could be applied to the problem.

“While reading our research article, we suddenly realized that the solution was before our eyes. Our next reaction was ‘oh no – we shot ourselves in the foot and gave the solution,'” says associate professor Eva Rotenberg of DTU.

About graph theory

A graph is a very simple construction that is used to model things that can be described as objects and the connections between them. Graphics theory is both an area of ​​mathematics and an important tool in computer science.

In this context, a graph can be illustrated by a diagram consisting of a number of points (nodes, vertices) connected by a number of lines (edges). Each edge is illustrated as a line (as a curved piece) with nodes as two endpoints.

About the solution

There are two types of updates in dynamic graphs: one can delete an edge and you can insert a new edge. These two operations must be performed by the user, while an algorithm keeps track of the network at all times. This is the algorithm that the researchers found the recipe for.

Could be used for computer electronics

This is when the two researchers were busy writing the research paper and tying loose ends to solve the conundrum that Holm had been working intermittently since 1998.

“We spent five to six weeks working non-stop on the article. And it ended up filling more than 80 pages,” says Eva Rotenberg.

Fortunately, no one came up with the solution and the two researchers were able to present their results at the most important theoretical computer science conferences, which were meant to be held in Chicago, but actually ended.

So, what solution can be used for this mathematical conundrum? The two researchers do not know for sure, but they have a few suggestions.

“Our research is basic research, so we rarely know where it will end up being used. Even from the beginning, we find applications difficult to think of,” says Jacob Holm, who added, “The design of microchips and circuit boards , found in all electronics, can be an area where our result ends up being used.When drawing wires on a circuit board they should never cross each other.Otherwise short circuits will occur.The same goes for microchips, which contain millions of transistors and for which one has to draw a graph. ”