Closing an Erdős Problem

Daniela Kühn is the Mason Professor in Mathematics at the University of Birmingham. She works in extremal and probabilistic combinatorics. She has many honors, including giving an invited lecture at the International Congress of Mathematicians in 2014.

Today I thought we should look at a new result of hers.

By the way, as I wrote this draft, I was excited to see that it was the second time we highlighted a researcher from Bi*ngham*. Previously we highlighted Jessica Fridrich, from Binghamton University. OK, they are different places, in different countries, but the closeness in edit distance caught my eye.

Kühn says here:

Recently I have focused on sufficient conditions for Hamilton cycles in directed graphs, i.e. cycles which contain all the vertices of the directed graph. It is unlikely that there is a good characterization of all (directed) graphs containing a Hamilton cycle since the corresponding decision problem is NP-complete. So it is natural to ask for sufficient conditions for the existence of a Hamilton cycle.

Here is her paper on degree sequences on directed graphs that force Hamilton cycles. It is joint with Deryk Osthus and Andrew Treglown.

The Conjecture

Paul Erdős is known for his conjectures as well as his countless results. Here are two of his open ones that are directly about graphs:

1. The Erdős-Faber-Lovász conjecture on coloring unions of cliques.
2. The Erdős-Hajnal conjecture that in a family of graphs defined by an excluded induced subgraph, every graph has either a large clique or a large independent set.

Of course math is tricky: A conjecture like the—

Erdős-Szekeres conjecture on the number of points needed to ensure that a point set contains a large convex polygon.

—could still be about graphs. Consider the graph that is

Well, the conjecture (1) is now claimed to be solved, and so the list of open conjectures is one less. Kühn with co-authors Dong Yeap Kang, Tom Kelly, Abhishek Methuku, and Deryk Osthus have claimed to resolve it. I have no reason to doubt these top researchers—it’s just until it is refereed. Their paper is cleverly titled: A Proof Of The Erdős-Faber-Lovász Conjecture.

By the way: See this talk on the paper by Kühn’s co-author Abhishek Methuku on this coming Monday March 22, 2021, 14:00 UTC. To see the talk on zoom you need to know the first six primes. Here is some help:

This conjecture, now almost 50 years old, states that a graph that consists of complete graphs of size that barely overlap can be colored with colors. Here barely overlap is they have no edge in common.

That is: If complete graphs, each having exactly vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be properly colored with colors. The following picture should help you understand the conjecture:

The conjecture can be stated various ways:
If are sets of size such that every pair of them shares at most one element, then the elements of each can be colored by colors so that all colors appear in each .
If H is a linear hypergraph with vertices, then the chromatic index of is at most .

The chromatic index of a hypergraph is the smallest number of colors needed to color the edges of so that any two edges that share a vertex have different colors.

Previous Results

While Kühn’s paper solves the conjecture, there were many partial results before. These prefer to view the conjecture as one about hypergraphs.

A linear hypergraph (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The cliques of size in the Erdős-Faber-Lovász conjecture may be interpreted as the hyperedges of an -uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős-Faber-Lovász conjecture states that, given any -uniform linear hypergraph with hyperedges, one may -color the vertices such that each hyperedge has one vertex of each color.

A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős-Faber-Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős-Faber-Lovász conjecture is equivalent to the statement that any simple hypergraph with vertices has chromatic index (edge coloring number) at most .

William Chang and Gene Lawler in their paper proved one of the first bounds. The goal is and they prove .

Call a hypergraph simple if for any pair of distinct vertices, there is at most one edge incident to both and , and there are no edges incident to exactly one vertex. A conjecture of Erdős, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph on vertices can be colored with at most colors. We present a simple proof that the edges of a simple hypergraph on vertices can be colored with at most colors.

Jeff Kahn showed that the bound could be improved to colors in this paper.

Open Problems

See Gil Kalai for his wonderful comments on this paper of Kühn and her co-authors.

Of course we congratulate Laci plus Avi Wigderson on winning the 2021 Abel Prize. We will write more about this in an upcoming post.