On the chromatic number of generalized Kneser hypergraphs

Abstract

The generalized Kneser hypergraph $K{G}^r(n,k,s)$ is the hypergraph whose vertices are all the $k$-subsets of $\{1,\dots ,n\}$, and edges are $r$-tuples of distinct vertices such that any pair of them has at most $s$ elements in their intersection. In this note, we show that for each non-negative integers $k,n,r,s$ satisfying $n\ge r(k-1)+1$, $k>s\ge 0$, and $r\ge 2$, we have $$\chi ({KG}^r(n,k,s))\ge \lceil \frac{n-r(k-s-1)}{r-1}\rceil ,$$ which improves the previously known result by Alon--Frankl--Lovász.