On Chromatic Number of Kneser Hypergraphs

Abstract

In this paper, in view of $Z_p$-Tucker lemma, we introduce a lower bound for chromatic number of Kneser hypergraphs which improves Dol'nikov-K{ř}{\'ı}{ž} bound. Next, we introduce multiple Kneser hypergraphs and we specify the chromatic number of some multiple Kneser hypergraphs. For a vector of positive integers $\vec{s}=(s_1,s_2,\dots ,s_m)$ and a partition $\pi =(P_1,P_2,\dots ,P_m)$ of $\{1,2,\dots ,n\}$, the multiple Kneser hypergraph ${\mathrm{KG}}^r(\pi ;\vec{s};k)$ is a hypergraph with the vertex set $$V=\left\{A:A\subseteq P_1\cup P_2\cup \cdots \cup P_m,|A|=k,\forall 1\le i\le m;|A\cap P_i|\le s_i\right\}$$ whose edge set is consist of any $r$ pairwise disjoint vertices. We determine the chromatic number of multiple Kneser hypergraphs provided that $r=2$ or for any $1\le i\le m$, we have $|P_i|\le 2s_i$. A subset $S\subseteq [n]$ is almost $s$-stable if for any two distinct elements $i,j\in S$, we have $|i-j|\ge s$. The almost $s$-stable Kneser hypergraph ${\mathrm{KG}}^r(n,k{)}_{s-stab}^{\sim }$ has all $s$-stable subsets of $[n]$ as the vertex set and every $r$-tuple of pairwise disjoint vertices forms an edge. Meunier [The chromatic number of almost stable Kneser hypergraphs. J. Combin. Theory Ser. A, 118(6):1820--1828, 2011] showed for any positive integer $r$, $\chi ({\mathrm{KG}}^r(n,k{)}_{2-stab}^{\sim })=\lceil \frac{n-r(k-1)}{r-1}\rceil$. We extend this result to a large family of Schrijver hypergraphs. Finally, we present a colorful-type result which confirms the existence of a completely multicolored complete bipartite graph in any coloring of a graph.

20 pages

Cited by in corpus (5)

• Strengthening topological colorful results for graphs
• A new lower bound for the chromatic number of general Kneser hypergraphs
• New construction of graphs with high chromatic number and small clique
• A Note on Altermatic Number
• Colorful hypergraphs in Kneser hypergraphs