We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
Mathematical Connect-the-Dots Reveals How Structure Emerges
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    graph theory

    Mathematical Connect-the-Dots Reveals How Structure Emerges

    By Leila Sloman

    June 23, 2022

    A new proof identifies precisely how large a mathematical graph must be before it contains a regular substructure.
    Comment
    Read Later
    Points connected by lines.

    In these 3-regular graphs, each point connects to exactly three lines.

    Kristina Armitage for Quanta Magazine

    By Leila Sloman

    Contributing Correspondent


    June 23, 2022


    View PDF/Print Mode
    Abstractions bloggraph theorymathematicsAll topics

    Introduction

    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 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.

    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).)

    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.”

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    By Leila Sloman

    Contributing Correspondent


    June 23, 2022


    View PDF/Print Mode
    Abstractions bloggraph theorymathematicsAll topics
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    An illustration that includes a triangular network overlaid by images of spinning particles.

    Next article

    The Spooky Quantum Phenomenon You’ve Never Heard Of
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023