QA484 : Some results in Kneser hypergraphs coloring
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2018
Authors:
Roya Abyazisani [Author], Meysam Alishahi[Supervisor]
Abstarct: Lovász ‎proved the long-standing Kneser conjecture in 1978.‎‎‎ This proof gave birth to an area of combinatorics called toplogical combinatorics which ‎concentrates ‎on coloring ‎properties of ‎Kneser graphs ‎and ‎hypergraphs.‎ The ‎general Kneser hypergraph KG^r (H) is an r-uniform hypergraph that somehow encodes the edge intersections of a ground hypergraph H‎.‎‎ ‎‎‎‎‎ We here define a new combinatorial parameter ‎called‎‎ equitable colorability defect of hypergraphs‎, which provides a new lower bound for‎ ‎the chromatic number of general Kneser hypergraphs.‎ We prove that our proposed sharp ‎lower ‎bound ‎outperforms ‎most ‎of ‎the best ‎known ‎existing ‎lower ‎bounds ‎for ‎‎chromatic number of hypergraph KG^r (H)‎.‎‎ In addition, we demonstrate that the difference between our proposed lower bound and some of the best known lower bounds such as the Dol'nikov-Kří ž lower bound (1992), the Ziegler lower bound (2002), and the Alishahi-Hajiabolhassan lower bound (2015) can be arbitrary large.‎ By use of the aforementioned lower bound, the chromatic number of some family of grahs is determined, as well.‎ ‎ Furthermore, we prove a result ensuring the existence of a colorful subhypergraph in any proper coloring of general Kneser hypergraphs that strengthens prior results in the literature.‎‎‎ We extend these results to categorical product of general Kneser hypergraphs.‎‎ To be more specific, we present some colorful type results for the coloring of‎ ‎categorical product of general Kneser hypergraphs‎, ‎which generalize the Hajiabolhassan-Meunier result (2016)‎.‎ Also‎, ‎we present a new lower bound for the chromatic number of categorical product of general Kneser hypergraphs which can be much better than the‎ ‎Hajiabolhassan-Meunier lower bound‎. ‎Using this lower bound‎, ‎we enrich the family of hypergraphs satisfying Zhu's conjecture (a generalization of ‎Hedetniemi's conjecture to hypergraphs)‎.
Keywords:
#Kneser ‎hypergraphs; ‎chromatic number; colorability defect; ‎colorful ‎subhypergraph; categorical product‎‎‎; ‎Hedetniemi's conjecture Link
Keeping place: Central Library of Shahrood University
Visitor: