# On splitting and splittable families

This post is a link to https://arxiv.org/abs/1811.12896

With Bryce Frederickson, Samuel Mathers, and Hao-Tong Yan.

*Abstract*: A set $A$ is said to *split* a finite set $B$ if exactly half the elements of $B$ (up to rounding) are contained in $A$. We study the dual notions: (1) a *splitting family*, a collection of sets such that any subset of ${1,\ldots,k}$ is split by a set in the family, and (2) a *splittable family*, a collection of sets such that there is a single set $A$ that splits each set in the family.

We study the minimum size of a splitting family on ${1,\ldots,k}$, as well as the structure of splitting families of minimum size. We use a mixture of computational and theoretical techniques. We additionally study the related notions of $\mathord{\leq}4$-splitting families and $4$-splitting families, and we provide lower bounds on the minimum size of such families.

Next we investigate splittable families that are just on the edge of unsplittability in several senses. First, we study splittable families that have the fewest number of splitters. We give a complete characterization in the case of two sets, and computational results in the case of three sets. Second, we define the *splitting game*, and study splittable families for which a splitter cannot be found under adversarial conditions.