Complexity and Characterization of Set Splitting

NEW

Problem: Reconstructed statement: Let $\mathcal B=\{B_1,\dots,B_n\}$ be a finite collection of finite sets. For each nonempty $I\subseteq[n]$, let

$$R_I=\{x\in\bigcup_iB_i: x\in B_i \iff i\in I\}.$$

If every $R_I$ is nonempty, then $\mathcal B$ is splittable: there is $S\subseteq\bigcup_iB_i$ such that

$$|S\cap B_i|\in\{\lfloor |B_i|/2\rfloor,\lceil |B_i|/2\rceil\} \quad\text{for all }i.$$

This matches Bernstein–Bortner–Coskey–Li–Simpson’s terminology: “splittable” means $1/2$-splittable, and Venn regions are indexed by nonempty membership patterns. If one also counts the outside region, it is irrelevant because it lies in no $B_i$.

Result: The conjecture is true.

Let $a_I=|R_I|\ge1$. It is enough to choose integers $d_I$ with

$$d_I\equiv a_I\pmod2,\qquad |d_I|\le a_I,$$

such that for every $i$,

$$\Delta_i:=\sum_{I\ni i}d_I$$

is $0$ when $|B_i|$ is even and is $\pm1$ when $|B_i|$ is odd. Then selecting $(a_I+d_I)/2$ elements from each $R_I$ gives a splitter.

Let

$$\mathcal P=\{I\ne\varnothing: a_I\text{ is odd}\}, \qquad q_i=|\{I\in\mathcal P:i\in I\}|.$$

Then $|B_i|\equiv q_i\pmod2$.

We use the standard Boolean-zonotope saturation fact: if $q$ is the degree vector of a simple hypergraph on $[n]$, then $c_i=\lceil q_i/2\rceil$ is also the degree vector of some simple hypergraph $\mathcal Q$ on $[n]$. Applying this to $\mathcal P$, choose $\mathcal Q$ with

$$|\{I\in\mathcal Q:i\in I\}|=\lceil q_i/2\rceil.$$

Now define

$$d_I= \begin{cases} 1-2\mathbf 1_{I\in\mathcal Q}, & I\in\mathcal P,\\ -2\mathbf 1_{I\in\mathcal Q}, & I\notin\mathcal P. \end{cases}$$

If $I\in\mathcal P$, then $d_I=\pm1$, allowed because $a_I$ is odd. If $I\notin\mathcal P$, then $a_I$ is even and positive, so $a_I\ge2$, and $d_I\in\{0,-2\}$ is allowed.

For each $i$,

$$\Delta_i =q_i-2\lceil q_i/2\rceil = \begin{cases} 0,&q_i\text{ even},\\ -1,&q_i\text{ odd}. \end{cases}$$

Since $|B_i|\equiv q_i\pmod2$, this gives exactly the required half, or the floor when $|B_i|$ is odd. Thus $\mathcal B$ is splittable.

Verification audit: no assumption beyond finiteness and nonempty nonzero Venn regions was added; even Venn-region sizes are handled using $a_I\ge2$; odd set sizes use the permitted floor/ceiling convention; the outside Venn region, if present, affects no $B_i$.

Citation: Definitions: Peter Bernstein, Cashous Bortner, Samuel Coskey, Shuni Li, Connor Simpson, “The set splittability problem,” Australas. J. Combin. 75(2):190–209, 2019; arXiv:1611.01542.
Auxiliary fact used: the saturation/normality of the Boolean zonotope, equivalently the degree-vector halving property for simple hypergraphs; see e.g. B. Sturmfels, Gröbner Bases and Convex Polytopes, AMS University Lecture Series 8, 1996, on normal affine semigroups from distributive/Boolean configurations.