48 citations · 68 across the 25 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.CC2023
The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv
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 (Tra…
cs.DS2023
On Finding Constrained Independent Sets in Cycles
Ishay Haviv
A subset of is called stable if it forms an independent set in the cycle on the vertex set . In 1978, Schrijver proved via a topological argument that…
cs.CC2023
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
Dror Chawin, Ishay Haviv
The orthogonality dimension of a graph over is the smallest integer for which one can assign a nonzero -dimensional real vector to each vertex of , such…