On the chromatic number of general Kneser hypergraphs

In a break-through paper, Lovász [20] determined the chromatic number of Kneser graphs. This was improved by Schrijver [27], by introducing the Schrijver subgraphs of Kneser graphs and showing that their chromatic number is the same as that of Kneser graphs. Alon, Frankl, and Lovász [2] extended Lovász's result to the usual Kneser hypergraphs and one of our main results is to extend this to a new family of general Kneser hypergraphs. Moreover, as a special case, we settle a question from Naserasr and Tardif [26].In 2011, Meunier introduced almost 2-stable Kneser hypergraphs and determined their chromatic number as an approach to a supposition of Ziegler [35] and a conjecture of Alon, Drewnowski, and Łuczak [3]. In this work, our second main result is to improve this by computing the chromatic number of a large family of Schrijver hypergraphs. Our last main result is to prove the existence of a completely multicolored complete bipartite graph in every coloring of a graph which extends a result of Simonyi and Tardos [29].The first two results are proved using a new improvement of the Dol'nikov–Kříž [7] and [18] bound on the chromatic number of general Kneser hypergraphs.