Balanced set coloring

Let $$\{S_1, S_2, ..., S_m\}$$ be a collection of subsets of some universe $$U$$, where each $$S_i$$ has even size (so does $$U$$).

We want to color the elements of $$U$$, either red or blue, such that each $$S_i$$ has as many blue elements as red elements (every set is balanced in terms of colors).

I am more interested in structural results than algorithmic ones. The goal is to understand what properties of the sets make such a coloring always possible (in particular, whether specific properties that we identified are sufficient).

• Does anyone know references of that type?

The problem seems related to set cover, hitting set, and hypergraph coloring, but none of the results I found so far actually address a similar question. Please feel free to suggest an alternative name or formulation in the comments.

• Hmm, yes you're right, I misremembered that each edge is covered. It might be useful to write your instance for getting sufficient conditions, I suspect the general problem is NP-Hard, but I don't see an obvious reduction anymore. Commented Nov 17, 2023 at 20:16
• I'm deleting my comment just to not confuse people. Commented Nov 17, 2023 at 20:17

I think this question is closely related to the term discrepancy. Here is the defintion. Given a universe $$U$$ a collection of sets $$\mathcal{A}=\{S_i\}$$ and a function $$\varphi:U\to\{-1,1\}$$. For $$S\in\mathcal{A}$$ define $$\varphi(S)=\sum_{v\in S} \varphi(v)$$, and $$\mathrm{disc}(\mathcal{A},\varphi)=\max_{S\in\mathcal{A}} |\varphi(A)|$$. Finally, define $$\mathrm{disc}(\mathcal{A})=\min_{\varphi:U\to\{-1,1\}} \mathrm{disc}(A,\varphi)$$.
For example, it can be shown using the probabilistic method (see first reference) that $$\mathrm{disc}(\mathcal{A})\leq \sqrt{2|U|\ln(2|\mathrm{A}|)}$$ I think better results are also known. More on can be found in