• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

European Journal of Combinatorics. 2019. Vol. 79C. P. 228-236.
Kiselev S., Balogh J., Cherkashin D.

We suggest a new method on coloring generalized Kneser graphs based on hypergraphs with high discrepancy and small number of edges. The main result is providing 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. Our method extends to Kneser hypergraphs as well