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

• Published in: Proceedings of the London Mathematical Society 2024-12, Vol.129 (6), p.n/a
• Main Authors: Kang, Dong Yeap, Kelly, Tom, Kühn, Daniela, Methuku, Abhishek, Osthus, Deryk
• Format: Article
• Language: English
• ISSN: 0024-6115; 1460-244X
• DOI: 10.1112/plms.70011

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