Mathematicians Settle the Erdős Coloring ConjectureFeedzy

In the fall of 1972, Vance Faber was a new professor at the University of Colorado. When two influential mathematicians, Paul Erdős and László Lovász, came for a visit, Faber decided to host a tea party. Erdős in particular had an international reputation as an eccentric and energetic researcher, and Faber’s colleagues were eager to meet him.

“While we were there, like at so many of these tea parties, Erdős would sit in a corner, surrounded by his fans,” said Faber. “He’d be carrying on simultaneous discussions, often in several languages about different things.”

Erdős, Faber, and Lovász focused their conversation on hypergraphs, a promising new idea in graph theory at the time. After some debate they arrived at a single question, later known as the Erdős-Faber-Lovász conjecture. It concerns the minimum number of colors needed to color the edges of hypergraphs within certain constraints.

“It was the simplest possible thing we could come up with,” said Faber, now a mathematician at the Institute for Defense Analyses’ Center for Computing Sciences. “We worked on it a bit during the party and said, ‘Oh well, we’ll finish this up tomorrow.’ That never happened.”

The problem turned out to be much harder than expected. Erdős frequently advertised it as one of his three favorite conjectures, and he offered a reward for the solution, which increased to $500 as mathematicians realized the difficulty. The problem was well known in graph theory circles and attracted many attempts to solve it, none of which were successful.

But now, nearly 50 years later, a team of five mathematicians has finally proved the tea-party musing true. In a preprint posted in January, they place a limit on the number of colors that could ever be needed to shade the edges of certain hypergraphs so that no overlapping edges have the same color. They prove that the number of colors is never greater than the number of vertices in the hypergraph.

The approach involves carefully setting aside some edges of a graph and randomly coloring others, a combination of ideas that researchers have wielded in recent years to settle a number of long-standing open problems. It wasn’t available to Erdős, Faber and Lovász when they dreamed up the problem. But now, staring at its resolution, the two surviving mathematicians from the original trio can take pleasure in the mathematical innovations their curiosity provoked.

“It’s a beautiful work,” said Lovász, of Eötvös Loránd University. “I was really pleased to see this progress.”

Just Enough Colors

As Erdős, Faber and Lovász sipped tea and talked math, they had a new graph-like structure on their minds. Ordinary graphs are built from points, called vertices, linked by lines, called edges. Each edge joins exactly two vertices. But the hypergraphs Erdős, Faber and Lovász considered are less restrictive: Their edges can corral any number of vertices.

This more expansive notion of an edge makes hypergraphs more versatile than their hub-and-spoke cousins. Standard graphs can only express relationships between pairs of things, like two friends in a social network (where each person is represented by a vertex). But to express a relationship between more than two people—like shared membership in a group—each edge needs to encompass more than two people, which hypergraphs allow.

However, this versatility comes at a price: It’s harder to prove universal characteristics for hypergraphs than for ordinary graphs.

“Many of the miracles [of graph theory] either vanish or things become much harder when you move to hypergraphs,” said Gil Kalai of IDC Herzliya and the Hebrew University of Jerusalem.

For instance, edge-coloring problems become harder with hypergraphs. In these scenarios, the goal is to color all the edges of a graph (or hypergraph) so that no two edges that meet at a vertex have the same color. The minimum number of colors needed to do this is known as the chromatic index of the graph.

The Erdős-Faber-Lovász conjecture is a coloring question about a specific type of hypergraph where the edges overlap minimally. In these structures, known as linear hypergraphs, no two edges are allowed to overlap at more than one vertex. The conjecture predicts that the chromatic index of a linear hypergraph is never more than its number of vertices. In other words, if a linear hypergraph has nine vertices, its edges can be colored with no more than nine colors, regardless of how you draw them.

Read More