Erdős-Faber-Lovász conjecture: a simple hypergraph on \(n\) vertices has chromatic index at most \(n\)

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

We say that a hypergraph \( H\) (with vertex set \( V\)) is simple if no two edges of \( H\) have more than one vertex in common. In order to avoid trivialities, we will assume \( H\) has no singleton edges. By the chromatic index \( \chi'(H)\) of \( H\), we mean the least integer \( t\) such that there is a \( t\)-coloring of the edges of \( H\) with the property that intersecting edges have distinct colors. One of Erdös' favorite combinatorial problems is the (by now) classic [3]:

Erd\H{os-Faber-Lovász conjecture} [3], 1972 ($500)

Any simple hypergraph \(H\) on \(n\) vertices has chromatic index at most \(n\).

An equivalent formulation is the following [2]:

Let \( G_1, \dots, G_n\) be \( n\) edge-disjoint complete graphs on \( n\) vertices. Then the chromatic number of \( \cup_{i=1}^n G_i\) is \( n\).

There is yet another nice equivalent formulation:

Let \( A_1, \ldots, A_n\) denote \( n\) sets each of size \( n\). Suppose \( \vert A_i \cap A_j\vert \leq 1\) for \( i \not = j\). Then the elements can be colored in \( n\) colors such that each set \( A_i\) consists of elements of distinct colors.

Erdös liked to tell the story that when the authors first came up with the conjecture, they were sure that it must be trivial. They soon realized that it was going to be harder than they thought. Now, more than 25 years later, it seems they were right -- it is harder than they initially thought.

Observe that the upper bound of \( n\) can be achieved, eg., when \( H\) is a projective plane or a complete graph on \( n\) vertices with \( n\) odd. Kahn [5] has recently shown that the conjecture is asymptotically correct by proving that

\(\displaystyle \chi'(H) \leq n + o(n). \)

(For this outstanding result, he received \(250\) from Erd ös). Several people, including Berge [1] and Füredi [4] have suggested that the following stronger bound may hold:

If \( H\) is a simple hypergraph on \( n\) vertices, then

\(\displaystyle \chi'(H) \leq \max_{x \in V} \vert \bigcup_{A, x \in A} A\vert. \)

Kahn's proof actually gives

\(\displaystyle \chi'(H) \leq (1+o(1)) \max_{x \in V} \vert\bigcup_{A, x \in A} A \vert. \)

For an excellent survey of the research spawned by this (and several earlier) hypergraph conjectures of Erdös and his coauthors, the reader is directed to the insightful paper of Kahn [6].

Erdös also asked the question of determining \( \cup_{i=1}^n G_i\) if we require that \( G_i \cap G_j\), \( i \not = j\), is triangle-free, or should have at most one edge.

1 C. Berge. On the chromatic index of a linear hypergraph and the Chvátal conjecture. Combinatorial Mathematics, Proc. 3rd Int'; Conf. (New York, 1985), Ann. N. Y. Acad. Sci. 555, New York 1989, 40-44.

2 M. Deza, P. Erdös and P. Frankl. Intersection properties of systems of finite sets. Proc. London Math. Soc. (3) 36 (1978) no. 2, 369-384.

3 P. Erdös, Problems and results in graph theory and combinatorial analysis, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), 153-163, Academic Press, New York-London, 1979.

4 Z. Füredi. The chromatic index of simple hypergraphs. Graphs and Combinatorics 2 (1986), 89-92.

5 J. Kahn, Coloring nearly-disjoint hypergraphs with \( n+o(n)\) colors, J. Comb. Theory Ser. A 59 (1992), 31-39.

6 J. Kahn, On some hypergraph problems of Paul Erdös and the asymptotics of matchings, covers and colorings, The Mathematics of Paul Erdös, I (R. L. Graham and J. Nešetril, eds.), 345-371, Springer-Verlag, Berlin, 1996.