2020/02/05 by Azarpendar, Soheil, Jafari, Amir
#Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.01748
In this paper, we prove a generalization of a conjecture of Erdös, about the chromatic number of certain Kneser-type hypergraphs. For integers n,k,r,s with n≥ rk and 2≤ s≤ r, the r-uniform general Kneser hypergraph KGrs(n,k), has all k-subsets of \1,…,n\ as the vertex set and all multi-sets \A1,…, Ar\ of k-subsets with s-wise empty intersections as the edge set. The case r=s=2, was considers by Kneser \citeK in 1955, where he conjectured that its chromatic number is n-2(k-1). This was finally proved by Lovász \citeL in 1978. The case r>2 and s=2, was considered by Erdös in 1973, and he conjectured that its chromatic number is \lceil(n-r(k-1))/(r-1)\rceil. This conjecture was proved by Alon, Frankl and Lovász \citeAFL in 1986. The case where s>2, was considered by Sarkaria \citeS in 1990, where he claimed to prove a lower bound for its chromatic number which generalized all previous results. Unfortunately, an error was found by Lange and Ziegler \citeZ' in 2006 in the induction method of Sarkaria on the number of prime factors of r, and Sarkaria's proof only worked when s is less than the smallest prime factor of r or s=2. In this paper, by applying the \mathbb Zp-Tucker lemma of Ziegler \citeZ and Meunier \citeM, we finally prove the general Erdös conjecture and prove the claimed result of Sarkaria for any 2≤ s≤ r. We also provide another proof of a special case of this result, using methods similar to those of Alon, Frankl, and Lovász \citeAFL and compute the connectivity of certain simplicial complexes that might be of interest in their own right.