A new lower bound for the chromatic number of general Kneser hypergraphs. (June 2018)

• Record Type: Journal Article
• Authors: Abyazi Sani, Roya; Alishahi, Meysam
• Is Part Of: European journal of combinatorics. Volume 71(2018)
• Page Start: 229
• Page End: 245
• Publication Date: 2018-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.03.007
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: A general Kneser hypergraph KG r ( H ) is an r -uniform hypergraph that somehow encodes the edge intersections of a ground hypergraph H . The colorability defect of H is a combinatorial parameter providing a lower bound for the chromatic number of KG r ( H ), which is addressed in a series of works by Dol'nikov (1988), Kříž (1992) and Ziegler (2002). In this paper, we define a new combinatorial parameter, the equitable colorability defect of hypergraphs, which provides some common improvements upon these works. Roughly speaking, we propose a new lower bound for the chromatic number of general Kneser hypergraphs which substantially improves Ziegler's lower bound. It is always as good as Ziegler's lower bound and several families of hypergraphs for which the difference between these two lower bounds is arbitrary large are provided. This specializes to a substantial improvement of the Dol'nikov–Kříž lower bound for the chromatic number of general Kneser hypergraphs as well. Furthermore, we prove a result ensuring the existence of a colorful subhypergraph in any proper coloring of general Kneser hypergraphs that strengthens Meunier's result (Meunier, 2014).