Balanced set coloring

Question

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.

Answer 1

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

1. The Probabilistic Method by Noga Alon and Joel H. Spencer (Chapter 13 in the 4th edition).
2. Geometric Discrepancy by Jiřı́ Matoušek.