Lower bounds for the chromatic number of certain Kneser-type hypergraphs

Abstract

Let $n\ge 1$, $r\ge 2$, and $s\ge 0$ be integers and $\mathcal{P}=\{P_1,\dots ,P_l\}$ be a partition of $[n]=\{1,\dots ,n\}$ with $|P_i|\le r$ for $i=1,\dots ,l$. Also, let $\mathcal{F}$ be a family of non-empty subsets of $[n]$. The $r$-uniform Kneser-type hypergraph $\mbox{KG}^r({\cal F}, {\cal P},s)$ is the hypergraph with the vertex set of all $\mathcal{P}$-admissible elements $F\in \mathcal{F}$, that is $|F\cap P_i|\le 1$ for $i=1,\dots ,l$ and the edge set of all $r$-subsets $\{F_1,\dots ,F_r\}$ of the vertex set that $|F_i\cap F_j|\le s$ for all $1\le i<j\le r$. In this article, we extend the equitable $r$-colorability defect $\mbox{ecd}^r({\cal F})$ of Abyazi Sani and Alishahi to the case when one allows intersection among the vertices of an edge. It will be denoted by $\mbox{ecd}^r({\cal F},s)$. We then, give (under certain assumptions) lower bounds for the chromatic number of $\mbox{KG}^r({\cal F}, {\cal P},s)$ and some of its variants in terms of $\mbox{ecd}^r({\cal F},\lfloor s/2\rfloor)$. This work generalizes many existing results in the literature of the Kneser hypergraphs. It generalizes the previous results of the current authors from the special family of all $k$-subsets of $[n]$ to a general family $\mathcal{F}$ of subsets.

An error in the proof of the main theorem is fixed by weakening the statement of the theorem. Typos are fixed throughout the text