2018/05/29 by Daneshpajouh, Hamid Reza
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1805.11421
The generalized Kneser hypergraph KGr(n,k,s) is the hypergraph whose vertices are all the k-subsets of \1,… ,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 ≥ r(k-1)+1, k > s≥ 0, and r≥ 2, we have χ(KGr(n,k,s))≥\lceil(n-r(k-s-1))/(r-1)\rceil, which improves the previously known result by Alon--Frankl--Lovász.