Boise Algebra, Geometry, and Combinatorics Seminar, Boise, September 2016

Abstract: The set splittability problem asks whether, given a collection of finite sets, there exists a single set that selects exactly half the elements from each set in the collection. If a set has odd size, we may select either the floor or the ceiling of half its elements. The question is naturally a part of combinatorial discrepancy theory, since a collection is splittable if and only if its discrepancy is at most 1. In this talk we will show that the set splittability problem is NP complete. On the other hand, we will give several partial solutions to the problem for small collections and other special collections. This work was completed during our REU program in collaboration with P. Bernstein, C. Bortner, S. Li, and C. Simpson.