Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)
Imagine friend groups, each with at most people, where any two groups share at most one common member. Erdős, Faber and Lovász conjectured in 1972 that you can always give every person a role name from a list of only names so that within each group, everyone has a different name -- the same bound that would trivially be needed if the groups never overlapped at all. This deceptively simple statement about overlapping cliques turned out to resist proof for nearly fifty years.
Kang, Kelly, Kuhn, Methuku and Osthus (2023, Introduction) recall that in 1972 Erdős, Faber and Lovász conjectured three equivalent statements (see Section 1.1), of which the graph-theoretic reading is: if a graph is the union of cliques, each of size at most , such that every pair of cliques shares at most one vertex, then the chromatic number of is at most . The equivalent hypergraph-colouring formulation, which the paper works with throughout, is: for a linear hypergraph (one where any two edges share at most one vertex) on vertices, the chromatic index -- the minimum number of colours needed to colour the hyperedges so that intersecting edges get different colours -- satisfies . Erdős called this one of his three favourite combinatorial problems and, as its difficulty became apparent, offered escalating rewards that eventually reached 500 dollars.
- Linear hypergraph
- A hypergraph in which every two distinct hyperedges intersect in at most one vertex; ordinary graphs (all edges of size ) are automatically linear.
- Chromatic index
- The minimum number of colours needed to colour the (hyper)edges of a (hyper)graph so that any two edges sharing a vertex get different colours.