The Chromatic Number of Kneser Hypergraphs
N ALON, Péter Frankl, L. Lovász · Transactions of the American Mathematical Society · 1986
Suppose the $r$-subsets of an $n$-element set are colored by $t$ colors. THEOREM 1.1. If $n \geq (t - 1)(k - 1) + k \cdot r$, then there are $k$ pairwise disjoint $r$-sets having the same color. This was conjectured by Erdös $[{\mathbf {E}}]$ in 1973. Let $T(n, r, s)$ denote the Turán number for $s$-uniform hypergraphs (see $\S 1$). THEOREM 1.3. If $\varepsilon > 0, t \leq (1 - \varepsilon )T(n, r, s)/(k - 1)$, and $n > {n_0}(\varepsilon , r, s, k)$, then there are $k$ $r$-sets ${A_1},{A_2}, \ldots ,{A_k}$ having the same color such that $\left | {{A_i} \cap {A_j}} \right | < s$ for all $1 \leq i < j \leq k$. If $s = 2, \varepsilon$ can be omitted. Theorem 1.1 is best possible. Its proof generalizes Lovász’ topological proof of the Kneser conjecture (which is the case $k = 2$). The proof uses a generalization, due to Bárány, Shlosman, and Szücs of the Borsuk-Ulam theorem. Theorem 1.3 is best possible up to the $\varepsilon$-term (for large $n$). Its proof is purely combinatorial, and employs results on kernels of sunflowers.