MathLabs

Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)

Step 1 of 8: Erdős's 500-dollar problem: coloring overlapping cliques
In plain words

Imagine nn friend groups, each with at most nn 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 nn names so that within each group, everyone has a different name -- the same bound nn 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.

χ′(H)≤n\chi'(\mathcal{H}) \le n
Detailed analysis

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 GG is the union of nn cliques, each of size at most nn, such that every pair of cliques shares at most one vertex, then the chromatic number of GG is at most nn. The equivalent hypergraph-colouring formulation, which the paper works with throughout, is: for a linear hypergraph H\mathcal{H} (one where any two edges share at most one vertex) on nn vertices, the chromatic index χ′(H)\chi'(\mathcal{H}) -- the minimum number of colours needed to colour the hyperedges so that intersecting edges get different colours -- satisfies χ′(H)≤n\chi'(\mathcal{H}) \le n. 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.

Terms in this step
Linear hypergraph
A hypergraph H\mathcal{H} in which every two distinct hyperedges intersect in at most one vertex; ordinary graphs (all edges of size 22) are automatically linear.
Chromatic index
The minimum number of colours χ′(H)\chi'(\mathcal{H}) needed to colour the (hyper)edges of a (hyper)graph so that any two edges sharing a vertex get different colours.
Knowledge used in this step