Contents Online

# Journal of Combinatorics

## Volume 13 (2022)

### Number 3

### On the chromatic number of almost stable general Kneser hypergraphs

Pages: 437 – 444

DOI: https://dx.doi.org/10.4310/JOC.2022.v13.n3.a5

#### Author

#### Abstract

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.

Received 15 December 2020

Accepted 10 April 2021

Published 31 March 2022