Mathematicians establish the Erdős coloring hypothesis
In the fall In 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, Faber decided to organize a tea party. Erdős had an international reputation as an eccentric and energetic researcher, and Faber’s colleagues were eager to get to know him.
“While we were there, as in many of these tea parties, Erdős was sitting in a corner, surrounded by his fans,” Faber said. “He was going to have simultaneous discussions, often about different things in different languages.”
Erdős, Faber, and Lovász focused the interview on hypergraphs, a new idea of great future in the theory of graphs of the time. After some discussion they came to a single question, later known as the Erdős-Faber-Lovász conjecture. It is about the minimum number of colors required to paint the edges of hypergraphs within certain boundaries.
“It was the easiest thing we could do,” said Faber, now a mathematician at the Center for Computer Science at the Institute of Defense Analysis. “We practiced a bit during the party and said, ‘Well, we’re going to finish this tomorrow.’ That never happened.”
The problem was much harder than expected. Erdős often advertised it as one of his three favorite assumptions, and offered the prize for the solution, which came to $ 500 as mathematicians realized the difficulty. The problem was well known in the circles of graph theory and attracted many attempts to solve it, none of which was successful.
But now, almost 50 years later, a team of five mathematicians has finally proven that the tea party is true. In one prepress published in January, limit the number of colors that may ever be needed to turn off the edges of certain hypergraphs so that the overlapping edges do not have the same color. They have shown that the number of colors is never greater than the number of vertices in a hypergraph.
The approach involves carefully discarding some edges of a graph and painting others at random, a combination of the ideas that researchers have. armed in recent years to solve several long-standing open problems. Erdős, Faber and Lovász were not available when they invented the problem. But now, looking at his resolution, the two surviving mathematicians from the original trio can take pleasure in the mathematical innovations that have sparked curiosity.
“It’s a beautiful job,” he said Groom, Eötvös Loránd University. “I was really excited to see that progress.”
While Erdős, Faber, and Lovász were drinking tea and talking about math, they had a new graphic-like structure in mind. Ordinary graphs are constructed from points called vertices, connected by lines, called edges. Each edge joins exactly two vertices. But the hypergraphs of Erdős, Faber, and Lovász are not so restrictive: their edges can straighten many vertices.
This broader notion of edge makes hypergraphs more flexible than their cousins ’mouthpieces. Standard graphs can only represent relationships between pairs of things, like two friends on a social network (each person is represented by a vertex). But to express a relationship between more than two people — like shared participation in a group — each edge must bring together more than two people, which is allowed by hypergraphs.
However, this variability comes at a price: it is more difficult to prove the universal characteristics of hypergraphs than for ordinary graphs.
“A lot of miracles [of graph theory] it’s gone or things get a lot harder when you go to hypergraphs, ”he said Gil Kalai IDC Herzliya and the Hebrew University of Jerusalem.
For example, problems coloring edges are harder with hypergraphs. In these scenarios, the goal is to paint all the edges of a graph (or hypergraph) so that the two edges that meet at a vertex do not have the same color. The minimum number of colors required for 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 the least. In these structures known as linear hypergraphs no two edges are added at more than one vertex. The assumption predicts that the chromatic index of a linear hypergraph is never greater than the number of vertices. In other words, if a linear hypergraph has nine vertices, its edges can be colored with more than nine colors, regardless of how you drew them.