Mathematicians settle Erdős coloring conjecture

In autumn from 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 to visit us, Faber decided to organize 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 was sitting in a corner, surrounded by his fans,” Faber said. “He was having simultaneous discussions, often in several languages ​​on different topics.”

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 came to a single question, later known as the Erdős-Faber-Lovász conjecture. This is the minimum number of colors needed to color the edges of hypergraphs under certain constraints.

“It was the simplest thing possible that we could find,” said Faber, now a mathematician at the Center for Computer Science at the Institute for Defense Analyzes. “We worked on it a bit during the party and we were like, ‘Well, we’ll finish this tomorrow.’ It never happened.

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

But now, almost 50 years later, a team of five mathematicians has finally proven the tea reverie to be true. In one preprint posted in january, they put a limit on the number of colors that might be needed to shade the edges of some 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 of the hypergraph.

The approach involves carefully setting aside some edges of a graph and coloring others at random, a combination of ideas the researchers have. handled in recent years to address a number of long-standing issues. It was not available to Erdős, Faber and Lovász when they imagined the problem. But now, looking at his resolve, the two surviving mathematicians of the original trio can take pleasure in the mathematical innovations their curiosity sparked.

“It’s a great job,” said Young married man, from Eötvös Loránd University. “I was very happy to see this progress.”

Just enough colors

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

This broader notion of edge makes hypergraphs more versatile than their star cousins. Standard charts 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 – such as shared group membership – each edge must encompass more than two people, which hypergraphs allow.

However, this versatility comes at a price: it is more difficult to prove the universal characteristics of hypergraphs than ordinary graphics.

“Lots of miracles [of graph theory] either go away or things get a lot more difficult when you switch to hypergraphs, ”said Gil Kalai of IDC Herzliya and the Hebrew University of Jerusalem.

For example, edge staining problems become more difficult with hypergraphs. In these scenarios, the goal is to color all the edges of a graph (or hypergraph) so that no edge that meets at a vertex has the same color. The minimum number of colors needed to do this is called the color index of the chart.

The Erdős-Faber-Lovász conjecture is a matter of coloring on a specific type of hypergraph where the edges overlap minimally. In these structures, called linear hypergraphs, two edges are not allowed to overlap at more than one vertex. The conjecture predicts that the chromatic index of a linear hypergraph is never greater 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.

Source link

Leave a Reply

Your email address will not be published. Required fields are marked *