2017/10/25 by Frick, Florian · 2 citations
#05C15 #52A35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.09434
Kneser's 1955 conjecture -- proven by Lovász in 1978 -- asserts that in any partition of the k-subsets of \1, 2, …, n\ into n-2k-3 parts, one part contains two disjoint sets. Schrijver showed that one can restrict to significantly fewer k-sets and still observe the same intersection pattern. Alon, Frankl, and Lovász proved a different generalization of Kneser's conjecture for r pairwise disjoint sets. Dolnikov generalized Lovász' result to arbitrary set systems, while Kříž did the same for the r-fold extension of Kneser's conjecture. Here we prove a common generalization of all of these results. Moreover, we prove additional strengthenings by determining the chromatic number of certain sparse stable Kneser hypergraphs, and further develop a general approach to establishing lower bounds for chromatic numbers of hypergraphs using a combination of methods from equivariant topology and intersection results for convex hulls of points in Euclidean space.