The chromatic number of almost stable Kneser hypergraphs (Q543913): Difference between revisions

The Kneser hypergraph \(K^{r}(n,k)\) is an \(r\)-uniform hypergraph whose vertex set comprises all \(k\)-subsets of \([n]\), and hyperedges are \(r\)-tuples of disjoint subsets. \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] answered in the affirmative a long-standing Kneser conjecture that \(\chi (K^{2}(n,k))=n-2k+2.\) Later, this result was generalized by showing \(\chi (K^{r}(n,k))=\left\lceil \frac{ n-k(-1)r}{r-1}\right\rceil \). A subset \(S\subset [ n]\) is called \(2\)-stable if for any \(i,j\in S\), \(\left| i-j\right| \geq 2.\) It is proved in the paper that for \(p\) prime and \(n\geq kp,\) the chromatic number of the subgraph of \(K^{p}(n,k)\) induced by \(2\)-stable sets equals \(\chi (K^{r}(n,k)).\)