On Chromatic Number of Kneser Hypergraphs

In this paper, in view of $Z_p$-Tucker lemma, we introduce a lower bound for chromatic number of Kneser hypergraphs which improves Dol’nikov-K{\v{r}}{'{\i}}{\v{z}} bound. Next, we introduce multiple Kneser hypergraphs and we specify the chromatic number of some multiple Kneser hypergraphs. For a vector of positive integers $\vec{s}=(s_1,s_2,\dots ,s_m)$ and a partition $\pi =(P_1,P_2,\dots ,P_m)$ of $\{1,2,\dots ,n\}$, the multiple Kneser hypergraph ${\mathrm{K}\mathrm{G}}^r(\pi ;\vec{s};k)$ is a hypergraph with the vertex set $$V=\{A:A\subseteq P_1\cup P_2\cup \cdots \cup P_m,\mathrm{\mid }A\mathrm{\mid }=k,\mathrm{\forall }1\le i\le m;\mathrm{\mid }A\cap P_i\mathrm{\mid }\le s_i\}$$ whose edge set is consist of any $r$ pairwise disjoint vertices. We determine the chromatic number of multiple Kneser hypergraphs provided that $r=2$ or for any $1\le i\le m$, we have $\mathrm{\mid }{P}_i\mathrm{\mid }\le 2s_i$. A subset $S\subseteq [n]$ is almost $s$-stable if for any two distinct elements $i,j\in S$, we have $\mathrm{\mid }i-j\mathrm{\mid }\ge s$. The almost $s$-stable Kneser hypergraph ${\mathrm{K}\mathrm{G}}^r(n,k{)}_{s-stab}^{\sim }$ has all $s$-stable subsets of $[n]$ as the vertex set and every $r$-tuple of pairwise disjoint vertices forms an edge. Meunier [The chromatic number of almost stable Kneser hypergraphs. J. Combin. Theory Ser. A, 118(6):1820–1828, 2011] showed for any positive integer $r$, $\chi({\rm KG}^r(n,k)_{2-stab}^{\sim})=\left\lceil {n-r(k-1) \over r-1}\right\rceil$. We extend this result to a large family of Schrijver hypergraphs. Finally, we present a colorful-type result which confirms the existence of a completely multicolored complete bipartite graph in any coloring of a graph.