The chromatic number of almost stable Kneser hypergraphs (Q543913)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The chromatic number of almost stable Kneser hypergraphs
scientific article

    Statements

    The chromatic number of almost stable Kneser hypergraphs (English)
    0 references
    0 references
    17 June 2011
    0 references
    The Kneser hypergraph \(K^{r}(n,k)\) is an \(r\)-uniform hypergraph whose vertex set comprises all \(k\)-subsets of \([n]\), and hyperedges are \(r\)-tuples of disjoint subsets. \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] answered in the affirmative a long-standing Kneser conjecture that \(\chi (K^{2}(n,k))=n-2k+2.\) Later, this result was generalized by showing \(\chi (K^{r}(n,k))=\left\lceil \frac{ n-k(-1)r}{r-1}\right\rceil \). A subset \(S\subset [ n]\) is called \(2\)-stable if for any \(i,j\in S\), \(\left| i-j\right| \geq 2.\) It is proved in the paper that for \(p\) prime and \(n\geq kp,\) the chromatic number of the subgraph of \(K^{p}(n,k)\) induced by \(2\)-stable sets equals \(\chi (K^{r}(n,k)).\)
    0 references
    0 references
    0 references
    0 references
    0 references
    chromatic number
    0 references
    combinatorial topology
    0 references
    stable Kneser hypergraphs
    0 references
    \(Z_{p}\)-Tucker lemma
    0 references
    0 references
    0 references
    0 references