“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 14981 |
|
| 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 | |
