New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different

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?

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

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.

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

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

The post New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different first appeared on Quanta Magazine.