Portal de Periódicos da CAPES

The Chromatic Number of Kneser Hypergraphs

1986; American Mathematical Society; Volume: 298; Issue: 1 Linguagem: Inglês

10.2307/2000624

1088-6850

N. Alon, Péter Frankl, L. Lovasz,

Commutative Algebra and Its Applications

Suppose the r-subsets of an n-element set are colored by t colors.THEOREM 1.1.IJ n ~ (t -l)(k -1) + k .r, then there are k pairwise disjoint r-sets having the same color.This was conjectured by Erdos [El in 1973.Let T(n, r, s) denote the 'lUran number for s-uniform hypergraphs (see §1).THEOREM 1.3.IJe > 0, t ~ (1-e)T(n,r,s)/(k-1), andn > no(e,r,s,k), then there are k r-sets At, A2, .. ., Ak having the same color such that IAi n Ajl < s Jor all 1 ~ i < j ~ k.IJ s = 2, e can be omitted.Theorem 1.1 is best possible.Its proof generalizes Lovasz' topological proof of the Kneser conjecture (which is the case k = 2).The proof uses a generalization, due to Barany, Shlosman, and Szucs of the Borsuk-Ulam theorem.Theorem 1.3 is best possible up to the e-term (for large n).Its proof is purely combinatorial, and employs results on kernels of sunflowers. Introduction.Let n, k, r, t, s be positive integers and let X be an n-element set.We denote by (-;) the collection of all r-element subsets of X.Suppose that n ~ (kr -1) + (t -1)(k -1) and write X = Xo u• .. U Xt-t.whereIt is easy to check that none of these families contains k pairwise disjoint members, moreover, 1OU•••U.rt-l= (-;).Our first result states that such a partition does not exist for n > (kr -1)+ (t -1)(k -1).THEOREM 1.1.Suppose that n ~ kr+ (t-1)(k-1) and (-;) is partitioned into t families.Then one of the families contains k pairwise disjoint r-element sets.For k = 2 the statement of the theorem was conjectured by Kneser [Kn] and proved by Lovasz [Lt] (cf.also [Ba]).The validity of Theorem 1.1 was conjectured by ErdOs [E] in 1973 (cf.also [Gy]).The case r = 2 was proved by Cockayne and Lorimer [CL] and independently by Gyarfas [Gy].The case t = 2 was proved in [AF].Theorem 1.1 immediately implies the following extension.COROLLARY 1.2.Suppose kl ~ ... ~ kt ~ 2 and n ~ klr + L2<i<t(ki -1).If ( -;) = 1t U ... U .rt, then for some i, 1 ~ i ~ t, the family Ji contai~ ki pairwise disjoint members.