Generalized Kneser Coloring Theorems with Combinatorial Proofs (Erratum)
Günter M. Ziegler · 2005
In [5], we presented a lower bound for the chromatic numbers of hypergraphs KG sS, “generalized r-uniform Kneser hypergraphs with intersection multiplicities s.” It generalized previous lower bounds by Křiž [1, 2] for the case s = (1, . . . , 1) without intersection multiplicities, and by Sarkaria [4] for S = ([n] k ) . The following two problems that arise for intersection multiplicities si > 1 were noticed by Carsten Lange resp. by Karsten Vogel: 1. In the presence of intersection multiplicities, there are two different versions of a “Kneser hypergraph,” depending on whether one admits hypergraph edges that are multisets rather than sets. It is shown in [3] that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria [4] and of [5, Thm. 5.1] apply only to the multiset version. The coloring and upper bound of [5, Lemma 3.1] is also valid for the multiset version. The coloring of [5, Example 7.2] refers to the set version. 2. The reductions to the case of prime r in the proof for [5, Thm. 5.1] works only if the intersection multiplicities are strictly smaller than the largest prime factor of r. (Specifically, a problem arises in the reduction of [5, pp. 679-680] if the auxiliary set system T is empty.) Currently we have no valid proof for the lower bound result in the other cases. This also applies to the special case S = ([n] k ) of Sarkaria [4]. Details will be presented in [3].