Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree

Abstract

In 1977, Erdős asked the following question: for any integers $t,n\in \mathbb{N}$, if $G_1,\dots ,G_n$ are complete graphs such that each $G_i$ has at most $n$ vertices and every pair of them shares at most $t$ vertices, what is the largest possible chromatic number of the union ${\bigcup }_{i=1}^n{G}_i$? The equivalent dual formulation of this question asks for the largest chromatic index of an $n$-vertex hypergraph with maximum degree at most $n$ and maximum codegree at most $t$. For the case $t=1$, Erdős, Faber, and Lovász famously conjectured that the answer is $n$, which was recently proved by the authors for all sufficiently large $n$. In this paper, we answer this question of Erdős for $t\ge 2$ in a strong sense, by proving that every $n$-vertex hypergraph with maximum degree at most $(1-o(1))tn$ and maximum codegree at most $t$ has chromatic index at most $tn$ for any $t,n\in \mathbb{N}$. Moreover, equality holds if and only if the hypergraph is a $t$-fold projective plane of order $k$, where $n=k^2+k+1$. Thus, for every $t\in \mathbb{N}$, this bound is best possible for infinitely many integers $n$. This result also holds for the list chromatic index.

Final version, to appear in Proceedings of the London Mathematical Society (26 pages)