<p>I think this question is closely related to the term <em>discrepancy</em>.
Here is the defintion.
Given a universe <span class="math-container">$U$</span> a collection of sets <span class="math-container">$\mathcal{A}=\{S_i\}$</span> and a function <span class="math-container">$\varphi:U\to\{-1,1\}$</span>. For <span class="math-container">$S\in\mathcal{A}$</span> define <span class="math-container">$\varphi(S)=\sum_{v\in S} \varphi(v)$</span>, and <span class="math-container">$\mathrm{disc}(\mathcal{A},\varphi)=\max_{S\in\mathcal{A}} |\varphi(A)|$</span>.
Finally, define <span class="math-container">$\mathrm{disc}(\mathcal{A})=\min_{\varphi:U\to\{-1,1\}} \mathrm{disc}(A,\varphi)$</span>.</p>
<p>For example, it can be shown using the probabilistic method (see first reference) that
<span class="math-container">$$
\mathrm{disc}(\mathcal{A})\leq \sqrt{2|U|\ln(2|\mathrm{A}|)}
$$</span>
I think better results are also known. More on can be found in</p>
<ol>
<li>The Probabilistic Method by Noga Alon and Joel H. Spencer (Chapter 13 in the 4th edition).</li>
<li>Geometric Discrepancy by Jiřı́ Matoušek.</li>
</ol>

CC BY-SA 4.0
2023-11-19T16:38:00.483Z
Thanks, this concept is exactly what I was looking for! I will now search for sufficient conditions for a discrepancy of zero (and I'll accept the answer). In the meantime, if anyone knows something about sufficient conditions for a zero-discrepancy, please comment further.
Arnaud Casteigts
CC BY-SA 4.0
2023-11-19T10:47:03.123Z
2023-11-19T10:47:03.123Z
TheHolyJoker
<p>Let <span class="math-container">$\{S_1, S_2, ..., S_m\}$</span> be a collection of subsets of some universe <span class="math-container">$U$</span>, where each <span class="math-container">$S_i$</span> has even size (so does <span class="math-container">$U$</span>).</p>
<p>We want to color the elements of <span class="math-container">$U$</span>, either red or blue, such that each <span class="math-container">$S_i$</span> has as many blue elements as red elements (every set is <em>balanced</em> in terms of colors).</p>
<p>I am more interested in structural results than algorithmic ones. The goal is to understand what properties of the sets make such a coloring <em>always</em> possible (in particular, whether specific properties that we identified are sufficient).</p>
<ul>
<li>Does anyone know references of that type?</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2023-11-17T20:16:57.610Z
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.
user3508551
CC BY-SA 4.0
2023-11-17T20:17:10.470Z
I'm deleting my comment just to not confuse people.
user3508551
<graph-colouring><set-cover><hypergraphs>
Balanced set coloring
Arnaud Casteigts
# Balanced set coloring

(Asked by: username_0 on 2023-11-17)

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.

**Tags:** graph-colouring, set-cover, hypergraphs

> **Comments:**
> **username_1**: 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.  
> **username_1**: I'm deleting my comment just to not confuse people.  

---

## 1 answers

### Answer by username_2 on 2023-11-19. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, this concept is exactly what I was looking for! I will now search for sufficient conditions for a discrepancy of zero (and I'll accept the answer). In the meantime, if anyone knows something about sufficient conditions for a zero-discrepancy, please comment further.  

---

