Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

摘要

We suggest a new method for coloring generalized Kneser graphs based on hypergraphs with high discrepancy and a small number of edges. The main result provides a proper coloring of K(n, n/2 - t, s) in (4 + o(1))(s + t)(2) colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant.