With P. Bernstein, C. Bortner, S. Li, and C. Simpson. (arχiv)

Abstract: The set splittability problem is the following: given a finite collection of finite sets, does there exits a single set that selects half the elements from each set in the collection? (If a set has odd size, we allow the floor or ceiling.) It is natural to study the set splittability problem in the context of combinatorial discrepancy theory and its applications, since a collection is splittable if and only if it has discrepancy $\leq1$.

After introducing the concepts and their background, we show that the set splittability problem is NP-complete. We in fact establish this for the generalized version called the $p$-splittability problem, in which one seeks to select the fraction $p$ from each set instead of half. Next we investigate several criteria for splittability and $p$-splittability, giving a complete characterization of $p$-splittability for three sets and of splittability for four sets. Finally we show that when there are sufficiently many elements, unsplittability is asymptotically much more rare than splittability.