Mathematical Connect-the-Dots Reveals How Structure Emerges

Imagine 100 dots scattered in front of you. In a haphazard variation on connect-the-dots, start drawing lines between the points. How many lines can you draw without producing a triangle? A square? An 11-pointed star?

These types of problems have a long history in mathematics. In a paper posted on April 26, Oliver Janzer and Benny Sudakov of the Swiss Federal Institute of Technology Zurich have answered a 47-year-old version of the question. They consider an arrangement of dots and lines, called a graph by mathematicians. The structure they’re looking for is a special type of graph called a regular graph. In a regular graph, each point (or “node”) has the same number of lines (or “edges”) connected to it. In a 2-regular graph, every node sits on precisely two edges; it has “degree 2.” In a 600-regular graph, each node has degree 600.

If you start again with your 100 dots and keep adding edges, a portion of the dots and edges will eventually form regular graphs. At some threshold, their presence becomes unavoidable, just as triangles inevitably emerge when you try to place five edges among four nodes. Janzer and Sudakov figured out what this threshold was, answering a problem first asked in 1975 by Paul Erdős and Norbert Sauer.

“What really attracted me about this problem is this property that it’s very simple to state, it has a very old history, and it has a large number of immediate consequences,” said Janzer.

For 1- or 2-regular graphs, the answer to Erdős and Sauer’s problem was established long before 1975. That’s because these objects are very simple. A 1-regular graph can consist of two nodes and a single edge, so any nonempty graph qualifies. A 2-regular graph just needs a closed loop — think the outline of a polygon. But 3-regular graphs and higher are much more complex and varied in their structure. “The feeling was that once you solve the [3-regular] case, you will be able to solve the more general case,” said Gil Kalai, a professor at Reichman University and the Hebrew University of Jerusalem.

Erdős and Sauer already had some ideas about the 3-regular situation when they first published their problem. They were aware of graphs with n nodes and around 3n edges that did not have any 3-regular substructures. And they also knew that a graph with more than around n^8/5 edges had to have a 3-regular structure inside it. So the right threshold had to be somewhere between order n and order n^8/5, where “order n” just means n multiplied by some constant. But that still left a lot of possibilities.

László Pyber narrowed the options considerably in 1985 when he showed that the answer had to be less than order nlog(n), which is dramatically lower than n^8/5. (Here it’s worth mentioning that mathematicians care about what happens when a graph has an enormous number of points. If n is really big — say, 10¹⁰⁰ — then n^8/5 is about 10⁵⁸ times larger than nlog(n).)

Soon after that, Pyber, Vojtěch Rödl, and Endre Szemerédi built a graph with order nlog(log(n)) edges that did not contain a regular graph with degree 3 or more. As a consequence, the possible answers to Erdős and Sauer’s problem ranged from order nlog(log(n)) on the low end to order nlog(n) on the high end.

The question then stagnated for almost four decades until this March, when Janzer and Sudakov decided to attempt the problem. “This is one of those high-risk, high-reward problems,” said Janzer. “You’re not going to be sad if you don’t solve it, but sometimes you need to try.”

The pair began by delving into Pyber, Rödl, and Szemerédi’s paper, hoping to work out how those three managed to avoid producing a regular graph. On their graph, some nodes were connected to an enormous number of edges, while others were connected to just a few. These different types of nodes were tightly interconnected, making it impossible to extract a more regular substructure.

“The construction is kind of an inspiration because it kind of tells you, okay, this is what the barrier is,” said Jacques Verstraete, a mathematician at the University of California, San Diego who has collaborated with Sudakov.

Janzer and Sudakov discovered that if you add more edges — order nlog(log(n)) more — to create a denser version of Pyber, Rödl, and Szemerédi’s graph, the whole picture changes. Suddenly, regular graphs start to pop up. That feature allowed the two authors to unearth a regular graph from all types of graphs: Any graph with enough edges contains a graph that mimics one of these extra-dense Pyber-Rödl-Szemerédi structures, which in turn contains a regular graph.

That result allowed them to prove that on an n-node graph, order nlog(log(n)) edges will surely contain a regular graph with degree 3 or more. The order of the solution is the same whether you’re looking for a 3-regular graph or a 1,000,000-regular graph, although you might need many times more edges for the latter. And Pyber, Rödl, and Szemerédi’s long-ago result means the order can’t be made any smaller — definitively settling Erdős and Sauer’s question. “It’s remarkable that it’s not just an incremental improvement that they’ve made, they’ve solved the problem, which stood for more than 30 years,” said Verstraete.

Janzer and Sudakov have already found ways to apply their insight to other problems. For example, in 1983 the mathematician Carsten Thomassen published his own problem about graphs. Thomassen wanted to take a graph and extract a substructure that, among other requirements, avoids short loops of edges while making sure each node attaches to a certain number of edges. The exercise was already known to be possible if the original graph has enough edges to begin with; Janzer and Sudakov have lowered that ceiling. They’ve also used their work to contribute to one question from 1970 that predates the Erdős-Sauer problem.

For Sudakov, the paper offers a coda to a mathematical symphony started long ago. “It utilizes all of these works of the previous guys who worked on it,” he said. “It’s surprising that everybody who thought about this problem thought in the right direction.”