“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 14981
School of Mathematics
  Title:   Chromatic number of random kneser hypergraphs
  Author(s):  Hossein Hajiabolhassan (Joint with M. Alishahi)
  Status:   To Appear
  Journal: J. Combin. Theory Ser. A
  Supported by:  IPM
  Abstract:
Recently, Kupavskii [On random subgraphs of Kneser and Schrijver graphs. J. Combin. Theory Ser. A, 2016.] investigated the chromatic numbers of the random Kneser graph \KGn,k(ρ) and proved that, in many cases, the chromatic number of the random Kneser graph \KGn,k(ρ) and the Kneser graph \KGn,k are almost surely closed. He also marked the studying of the chromatic number of random Kneser hypergraphs \KGrn,k(ρ) as a very interesting problem. With the help of \Zp-Tucker lemma, a combinatorial generalization of the Borsuk-Ulam theorem, we generalize Kupavskii's result to random general Kneser hypergraphs by introducing an almost surely lower bound for the chromatic number of them. Roughly speaking, as a special case of our result, we show that the chromatic numbers of the random Kneser hypergraph \KGrn,k(ρ) and the Kneser hypergraph \KGrn,k are almost surely closed in many cases. Moreover, restricting to the Kneser and Schrijver graphs, we present a purely combinatorial proof for an improvement of Kupavskii's results.
Also, for any hypergraph \HH, we present a lower bound for the minimum number of colors required in a coloring of \KGr(H) with no monochromatic Kt,…,tr subhypergraph, where Kt,…,tr is the complete r-uniform r-partite hypergraph with t r vertices such that each of its parts has t vertices. This result generalizes the lower bound for the chromatic number of \KGr(H) found by the present authors [On the chromatic number of general Kneser hypergraphs. J. Combin. Theory, Ser. B, 2015.].

Download TeX format
back to top
scroll left or right