The chromatic number of kneser hypergraphs

Suppose the r-subsets of an r-element set are colored by t colors. THEOREM (FORMULA PRESENTED), then there are k pairwise disjoint r-sets having the same color. This was conjectured by Erdös [E] in 1973. Let T(n, r, s) denote the Turán number for s-uniform hypergraphs (see §1). THEOREM 1.3. If (FORMULA PRESENTED), and n > no (e, r, s, k), then there are (FORMULA PRESENTED) having the same color such that (FORMULA PRESENTED), e 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 Sziics of the Borsuk-Ulam theorem. Theorem 1.3 is best possible up to thε e-term (for large n). Its proof is purely combinatorial, and employs results on kernels of sunflowers.