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

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

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

such that for every $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

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

Now define

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$,

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.