The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv · ACM Transactions on Computation Theory · 2024
We show that the Consensus Division theorem implies lower bounds on the chromatic number of Kneser hypergraphs, offering a novel proof for a result of Alon, Frankl, and Lovász and for its generalization by Kříž. Our approach is applied to study the computational complexity of the total search problem Kneser p , which given a succinct representation of a coloring of a p -uniform Kneser hypergraph with fewer colors than its chromatic number asks to find a monochromatic hyperedge. We prove that for every prime p , the Kneser p problem with an extended access to the input coloring is efficiently reducible to a quite weak approximation of the Consensus Division problem with p shares. In particular, for p =2, the problem is efficiently reducible to any non-trivial approximation of the Consensus Halving problem on normalized monotone functions. We further show that for every prime p , the Kneser p problem lies in the complexity class PPA -p . As an application, we establish limitations on the complexity of the Kneser p problem, restricted to colorings with a bounded number of colors.