On the chromatic number of almost stable general Kneser hypergraphs

Let $n \geq 1$ and $s \geq 1$ be integers. An almost $s$-stable subset $A$ of $[n] = \lbrace 1, \dotsc , n \rbrace$ is a subset such that for any two distinct elements $i, j \in A$, one has $\lvert i - j \rvert \geq s$. For a family $\mathcal{F}$ of non-empty subsets of $[n]$ and an integer $r \geq 2$, the chromatic number of the $r$-uniform Kneser hypergraph $\mathrm{KG}^r (\mathcal{F})$, whose vertex set is $\mathcal{F}$ and whose edge set is the set of $\lbrace A_1, \dotsc , A_r \rbrace$ of pairwise disjoint elements in $\mathcal{F}$, has been studied extensively in the literature and Abyazi Sani and Alishahi were able to give a lower bound for it in terms of the equatable $r$-colorability defect, $\mathrm{ecd}^r (\mathcal{F})$. In this article, the methods of Chen for the special family of all $k$-subsets of $[n]$, are modified to give lower bounds for the chromatic number of almost stable general Kneser hypergraph $\mathrm{KG}^r (\mathcal{F}_s)$ in terms of $\mathrm{ecd}^s (\mathcal{F})$. Here $\mathcal{F}_s$ is the collection of almost $s$-stable elements of $\mathcal{F}$. We also propose a generalization of a conjecture of Meunier.

Keywords

chromatic number, Kneser hypergraphs, Tucker’s lemma, almost stable subsets

2010 Mathematics Subject Classification

Primary 05C15, 05E45. Secondary 05C65.

Full Text (PDF format)

Received 15 December 2020

Accepted 10 April 2021

Published 31 March 2022