Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The chromatic number of Kneser hypergraphs

Authors: N. Alon, P. Frankl and L. Lovász
Journal: Trans. Amer. Math. Soc. 298 (1986), 359-370
MSC: Primary 05C65; Secondary 05C15
MathSciNet review: 857448
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \S1$).

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\vert {{A_i} \cap {A_j}} \right\vert < 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C65, 05C15

Retrieve articles in all journals with MSC: 05C65, 05C15

Additional Information

Article copyright: © Copyright 1986 American Mathematical Society