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.
H2 – Heading Level 2
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.
Simply Grid
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.
H3 – Heading Level 3
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 n8/5 edges had to have a 3-regular structure inside it. So the right threshold had to be somewhere between order n and order n8/5, where “order n” just means n multiplied by some constant. But that still left a lot of possibilities.
Simply Masonry
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 n8/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, 10100 — then n8/5 is about 1058 times larger than nlog(n).)
H4 – Heading Level 4
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.”
Simply Justified
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.
H5 – Heading Level 5
“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.
Share Buttons on Hover
Showing Share Buttons
