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
New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    graph theory

    New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different

    By Steve Nadis

    April 26, 2021

    Researchers have proved a special case of the Erdős-Hajnal conjecture, which shows what happens in graphs that exclude anything resembling a pentagon.
    Comment
    Read Later

    Pablo Hurtado de Mendoza for Quanta Magazine

    By Steve Nadis

    Contributing Writer


    April 26, 2021


    View PDF/Print Mode
    combinatoricsgraph theorymathematicsRamsey theoryAll topics

    Introduction

    When you walk into a room full of people, you can speculate about all sorts of things, from political leanings to TV viewing habits. But if the room has at least six people, you can say something about them with absolute mathematical certainty, thanks to a 1930 theorem by Frank Ramsey: Among those people, there’s either a group of three who all know each other, or a group of three who have never met.

    The scope of Ramsey theory, which examines the patterns that emerge as a group gets larger, extends well beyond social gatherings. It also has direct and crucial implications for a branch of mathematics known as graph theory. These graphs consist of collections of points, or vertices, that may (or may not) be connected to each other by an edge — equivalent to people at a party who may (or may not) have met before. The size of a graph is set by n, the number of vertices it has. A portion of a graph in which every vertex is connected by an edge to every other vertex is, fittingly, called a clique. Conversely, a portion of a graph in which no vertex is connected to any other vertex is called an anticlique, or stable set.

    The mathematician Paul Erdős was prolific in this area, proving numerous theorems that set quantitative bounds on the size of the cliques and stable sets that can arise in Ramsey theory. But in a paper published in 1989, Erdős and his frequent collaborator András Hajnal raised a question that’s still not fully answered: If you take a big graph and insist that no subset of that graph’s vertices will have the exact pattern of edges and non-edges that match a smaller graph (known as an “induced subgraph”), will you automatically end up with a larger maximum clique or stable set than you’d see in a randomly drawn graph of the same size?

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

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters

    Samuel Velasco/Quanta Magazine

    Introduction

    If the Erdős-Hajnal conjecture is true, then graphs with forbidden induced subgraphs behave very differently from general graphs, according to Maria Chudnovsky of Princeton University. “It tells you that if you provide me with some very local information about the graph — information regarding a small number of vertices — then something global happens. If I forbid a certain small structure, then a huge structure will inevitably emerge.”

    The global consequences of local restrictions is a common theme in graph theory, said Timothy Gowers of the University of Cambridge. But “like many other conjectures that are relatively simple to state but surprisingly hard to solve, [this conjecture] seems to expose a gap in our understanding.”

    Now, in a February 2021 paper, Chudnovsky, Alex Scott of the University of Oxford, Paul Seymour of Princeton University and Sophie Spirkl of the University of Waterloo have made huge progress toward filling in that gap. They didn’t prove the whole conjecture, but they showed that it holds true for a critical induced subgraph singled out by Erdős and Hajnal. “We were all a little shocked,” Chudnovsky said. “We thought this would be the case that was false, and the conjecture would fall.”

    Gowers called the work “exciting,” and Vašek Chvátal of Concordia University said, “A number of good people have tried very hard over the years to solve this problem.”

    “This is a major result in graph theory,” added Fan Chung Graham, a mathematician at the University of California, San Diego.

    Slow Progress

    Although the Erdős-Hajnal conjecture is “fundamental and fascinating,” said Chvátal, proving it has turned out to be extremely difficult. So far, mathematicians have attacked it on a case-by-case basis, mostly starting with the smallest prohibited structures and moving up from there.

    But progress has been slow, with major results emerging about once every decade or two. That means the conjecture has only been confirmed in a handful of instances to date, including all those in which the excluded induced subgraph has four vertices or fewer.

    In 2005, Chudnovsky and Shmuel Safra of Tel Aviv University proved that the Erdős-Hajnal conjecture was upheld when the forbidden induced subgraph is a five-vertex structure known as the bull, which resembles an inverted triangle with two single-vertex horns on top. That left only two five-vertex configurations still open: the pentagon (or really any five-sided polygon), also called a five-cycle, and the five-vertex path, which consists of four line segments linked together, forming an open chain.

    Introduction

    Of the two outstanding problems, the five-cycle was the more prominent, because of the elevated status granted it by Erdős and Hajnal, and consequently by everyone else. “They thought that it was complicated enough that if you could settle that case, you could settle the conjecture for all cases,” said János Pach of the Rényi Institute of Mathematics in Budapest, who collaborated with both Erdős and Hajnal.

    Hajnal, among others, suspected that the conjecture would ultimately turn out to be false. And when he first started on this project, Seymour would have agreed. He thought the five-cycle case, in particular, would be the counterexample demonstrating that very point. But instead, the opposite occurred: He and his co-authors showed that barring this particular induced subgraph from a graph would invariably produce either a large clique or a stable set, exactly as prescribed by the Erdős-Hajnal conjecture.

    Black-and-white photo of Paul Erdős in front of a chalkboard; black-and-white photo of András Hajnal seated indoors
    Black-and-white photo of Paul Erdős in front of a chalkboard; black-and-white photo of András Hajnal seated indoors

    In 1989, Paul Erdős (left) and his frequent collaborator András Hajnal asked what happens to graphs if you exclude given substructures.

    George Csicsery; Courtesy of the Hungarian Academy of Sciences

    Introduction

    “It was a big surprise to me that it turned out to be true,” Seymour said. “There didn’t seem to be any reason for it to be true.”

    Combing for Results

    To reach their unexpected result, the team relied upon the classic technique of “proof by contradiction.” They assumed that there is a counterexample to the conjecture — a graph that does not contain a five-cycle anywhere but also does not have a sufficiently large clique or stable set, in defiance of Erdős-Hajnal. “We then tried to prove so many things about it that it can’t possibly exist,” Seymour said. And if the counterexample could not exist, that meant the conjecture must have been right in the first place.

    The actual argument, of course, is more involved. The team wasn’t interested in just any counterexample — they sought the smallest possible one, which is a common tactic in graph theory, Spirkl said. Mathematicians often find minimal counterexamples easier to work with because they can focus on those parts of the graph that are relevant to the problem at hand and temporarily ignore the rest.

    “The smallest counterexample has the property such that if I delete a single vertex, then it suddenly is not a counterexample anymore,” Spirkl said. The remaining graph, which has been reduced from n to n – 1 vertices, now has a clique or stable set that’s so big it no longer qualifies as a counterexample.

    The five-cycle proof also built on a 2020 paper from Pach and István Tomon that presented a method for finding certain structures called “combs” in a graph.

    To get a sense of what these combs look like, imagine a graph that contains something resembling a simple, wide-tooth comb with the teeth pointing upward. Let’s also assume there is a vertex directly above the comb, along with edges that connect it to the tips of all teeth. The object we’ve just described is similar to a comb in the mathematical sense: There, at the base of each tooth, lies a string of vertices that may have edges between them.

    If we look more closely at the edge between two such vertices, we can follow a path from that base up through the two parallel teeth (each constituting an edge). From there, we connect the tips of the teeth via separate edges to the single vertex above the comb, and the shape we’ve just traced out is actually a five-sided polygon.

    In their new paper, Chudnovsky and her colleagues refined Pach and Tomon’s method to show that every smallest counterexample contains, somewhere within it, a large comb. That implies that it must have a five-cycle — the one thing it’s not supposed to have. And of course, that means it’s not a counterexample at all. By showing that no counterexample to the conjecture could be found, the four collaborators proved that the conjecture must be true in this case.

    A Route to the Summit?

    Now that the five-cycle question is answered, could it lead to a proof of the full conjecture, as Erdős and Hajnal anticipated? “For a long time, the five-cycle seemed just as hard as the general question,” Seymour said. “The hope was that if we could do that, we could do the general question. But that hope has fizzled a bit.”

    “This proof doesn’t nearly bring us there,” Spirkl confessed. “At the moment it seems that we would need some significant new ideas.” But there is hope, she added. “It may be the first of a long series of steps.”

    “Solving the five-cycle case makes more people think that the general conjecture must be true,” Graham said. “Although no one has found a way to prove it yet, having a success like this helps spread the word.”

    Even on its own, the proof is still considered a major accomplishment — the biggest development concerning this conjecture in more than a decade, and one whose results are not solely limited to the five-cycle case. “The techniques they were forced to develop to solve this problem can be applied to other problems,” said Chvátal, “which is how we make progress in mathematics.”

    The four co-authors have already begun this process, proving in the same paper that the Erdős-Hajnal conjecture holds for other special cases, including the so-called five-cycle with a “hat” — a six-cycle with an extra edge that joins two vertices, forming a pentagon with a triangle (or hat) on top.

    Introduction

    But there is one induced subgraph in particular that many mathematicians have in their sights. “The five-vertex path has to be next,” Seymour said. “If you can’t do that, you’re still nowhere.”

    “There are definitely ideas from the five-cycle proof that seem useful for the five-vertex path,” Spirkl said, “but they wouldn’t take us all the way there.”

    Given that, at present, no one knows how to attack the conjecture as a whole, the only available option, Chudnovsky said, is “approaching this problem one case at a time. We do what we can do.”

    And of course, there’s always the chance that this piecemeal approach could yield a big payoff. “One reason we’re doing these special cases is that they might lead us to a counterexample,” said Seymour, which would show that the conjecture is false.

    Thirty-two years after it was first published, the Erdős-Hajnal conjecture has turned out to be “a surprisingly treacherous peak,” said Pach. “Chudnovsky, Scott, Seymour and Spirkl have settled this special case, but we still don’t know where we stand. From our present location, we cannot see the summit. Perhaps we are almost there. Perhaps we are less than halfway. We have to wait for the fog to lift.”

    By Steve Nadis

    Contributing Writer


    April 26, 2021


    View PDF/Print Mode
    combinatoricsgraph theorymathematicsRamsey theoryAll 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 of a demon’s face.

    Next article

    How Maxwell’s Demon Continues to Startle Scientists
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

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