On the chromatic number of almost stable general Kneser hypergraphs

Abstract

Let $n\ge 1$ and $s\ge 1$ be integers. An almost $s$-stable subset $A$ of $[n]=\{1,\dots ,n\}$ is a subset such that for any two distinct elements $i,j\in A$, one has $|i-j|\ge s$. For a family $\mathcal{F}$ of non-empty subsets of $[n]$ and an integer $r\ge 2$, the chromatic number of the $r$-uniform Kneser hypergraph $\mbox{KG}^r({\cal F})$, whose vertex set is $\mathcal{F}$ and whose edge set is the set of $\{A_1,\dots ,A_r\}$ 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, $\mbox{ecd}^r({\cal 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 $\mbox{KG}^r({\cal F}_s)$ in terms of $\mbox{ecd}^s({\cal 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.

Minor typos and inaccuracies are fixed