1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 17, 2023 at 20:16
  • $\begingroup$ I'm deleting my comment just to not confuse people. $\endgroup$ Nov 17, 2023 at 20:17

1 Answer 1

3
$\begingroup$

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.
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 19, 2023 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.