The chromatic number of almost stable Kneser hypergraphs

Abstract

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|\ge s$ We define almost $s$-stable Kneser hypergraph $K{G}^r{\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{s\text{-stab}}^{\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\ge kp$, the chromatic number of almost 2-stable Kneser hypergraphs $K{G}^p{\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{2\text{-stab}}^{\sim }$ is equal to the chromatic number of the usual Kneser hypergraphs $K{G}^p\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, 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 $K{G}^r{\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{2^{\mu (r)}\text{-stab}}^{\sim }$ is equal to the chromatic number of the usual Kneser hypergraphs $K{G}^r\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ for any $n\ge kr$, namely that it is equal to $\lceil \frac{n-(k-1)r}{r-1}\rceil .$

References in corpus (1)

• Combinatorial Stokes formulas via minimal resolutions