Mathematics – Combinatorics
Scientific paper
2005-04-29
Journal of Combinatorial Theory, Series A 114 (2007), pp. 159-166
Mathematics
Combinatorics
9 pages; added examples in Section 2; added reference ([11]), corrected minor typos; to appear in J. Combinatorial Theory, Ser
Scientific paper
In Ziegler (2002), the second author presented a lower bound for the chromatic numbers of hypergraphs $\KG{r}{\pmb s}{\calS}$, "generalized $r$-uniform Kneser hypergraphs with intersection multiplicities $\pmb s$." It generalized previous lower bounds by Kriz (1992/2000) for the case ${\pmb s}=(1,...,1)$ without intersection multiplicities, and by Sarkaria (1990) for $\calS=\tbinom{[n]}k$. Here we discuss subtleties and difficulties that arise for intersection multiplicities $s_i>1$: 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. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version. 2. The reductions to the case of prime $r$ in the proofs Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of $r$. Currently we have no valid proof for the lower bound result in the other cases. We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.
Lange Carsten
Ziegler Guenter M.
No associations
LandOfFree
On generalized Kneser hypergraph colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On generalized Kneser hypergraph colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On generalized Kneser hypergraph colorings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-402755