The chromatic number of almost stable Kneser hypergraphs

Details The chromatic number of almost stable Kneser hypergraphs The chromatic number of almost stable Kneser hypergraphs

2009-12-23

arxiv.org/abs/0912.4748v1

Mathematics

Combinatorics

Scientific paper

Let $V(n,k,s)$ be the set of $k$-subsets $S$ of $[n]$ such that for all $i,j\in S$, we have $|i-j|\geq s$ We define almost $s$-stable Kneser hypergraph $KG^r{{[n]}\choose k}_{s{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ to be the $r$-uniform hypergraph whose vertex set is $V(n,k,s)$ and whose edges are the $r$-uples of disjoint elements of $V(n,k,s)$. With the help of a $Z_p$-Tucker lemma, we prove that, for $p$ prime and for any $n\geq kp$, the chromatic number of almost 2-stable Kneser hypergraphs $KG^p {{[n]}\choose k}_{2{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ is equal to the chromatic number of the usual Kneser hypergraphs $KG^p{{[n]}\choose k}$, namely that it is equal to $\lceil\frac{n-(k-1)p}{p-1}\rceil.$ Defining $\mu(r)$ to be the number of prime divisors of $r$, counted with multiplicities, this result implies that the chromatic number of almost $2^{\mu(r)}$-stable Kneser hypergraphs $KG^r{{[n]}\choose k}_{2^{\mu(r)}{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ is equal to the chromatic number of the usual Kneser hypergraphs $KG^r{{[n]}\choose k}$ for any $n\geq kr$, namely that it is equal to $\lceil\frac{n-(k-1)r}{r-1}\rceil.$

Affiliated with

Also associated with

No associations

Rating

The chromatic number of almost stable Kneser hypergraphs 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 The chromatic number of almost stable Kneser hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The chromatic number of almost stable Kneser hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-554269