Posts
Kelsey Houston-Edwards, Ph.D Student observes, Fifty years ago, Paul Erdős and two other mathematicians came up with a graph theory problem that they thought they might solve on the spot. A team of mathematicians has finally settled it.
The authors combined many techniques to create an algorithm that
covers all types of linear hypergraphs. Above, notes they made during
the process.
The authors combined many techniques to create an algorithm that covers all types of linear hypergraphs. Above, notes they made during the process.
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...
The extreme generality of the Erdős-Faber-Lovász conjecture makes it challenging to prove. As you move to hypergraphs with more and more vertices, the ways of arranging their looping edges multiply as well. With all these possibilities, it might seem likely that there is some configuration of edges that requires more colors than it has vertices.
“There are so many different types of hypergraphs that have completely different flavors,” said Abhishek Methuku, one of the authors of the new proof, along with Dong-yeap Kang, Tom Kelly, Daniela Kühn and Deryk Osthus, all of the University of Birmingham. “It is surprising that it is true.”
...Their strategy for coloring the large edges relied on a simplification. They reconfigured these edges as the vertices of an ordinary graph (where each edge only connects two vertices). They colored them using established results from standard graph theory and then transported that coloring back to the original hypergraph.
Source: Quanta Magazine
