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 (Trans. Amer. Math. Soc., 1986) and for its generalization by Kříž (Trans. Amer. Math. Soc., 1992). 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 \(\mathsf {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.

The Chromatic Number of Kneser Hypergraphs via Consensus Division

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
COMPUTER SCIENCE, THEORY & METHODS	3