2009/12/23 by Frédéric Meunier, Meunier, Frédéric · 1 citation
Computer Science · Mathematics · #05C65 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.0912.4748
openalex publication_date 2009/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let V(n,k,s) be the set of k-subsets S of [n] such that for all i,j∈ S, we have |i-j|≥ s We define almost s-stable Kneser hypergraph KGr[n]\choose k_s\tiny\textup-stab∼ to be the r-uniform hypergraph whose vertex set is V(n,k,s) and whose edges are the r-uples of disjoint elements of V(n,k,s). With the help of a Zp-Tucker lemma, we prove that, for p prime and for any n≥ kp, the chromatic number of almost 2-stable Kneser hypergraphs KGp [n]\choose k_2\tiny\textup-stab∼ is equal to the chromatic number of the usual Kneser hypergraphs KGp[n]\choose k, namely that it is equal to \lceil(n-(k-1)p)/(p-1)\rceil. Defining μ(r) to be the number of prime divisors of r, counted with multiplicities, this result implies that the chromatic number of almost 2μ(r)-stable Kneser hypergraphs KGr[n]\choose k_2μ(r)\tiny\textup-stab∼ is equal to the chromatic number of the usual Kneser hypergraphs KGr[n]\choose k for any n≥ kr, namely that it is equal to \lceil(n-(k-1)r)/(r-1)\rceil.