The chromatic number of kneser hypergraphs

N. Alon, P. Frankl, L. Lovasz

Research output: Contribution to journalArticle

64 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)359-370
Number of pages12
JournalTransactions of the American Mathematical Society
Volume298
Issue number1
DOIs
StatePublished - Nov 1986

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The chromatic number of kneser hypergraphs'. Together they form a unique fingerprint.

  • Cite this