Let $S_1,S_2,\dots,S_k$ be subsets of the set $S=\{1,2,\dots,n\}$, not necessarily distinct. We will color each element of $S$ red, green, or blue. From this coloring, each set $S_i$ will receive one or more color according to the following rule:

Let $r_i,g_i,b_i$ denote the number of red, green, and blue elements of $S_i$, respectively, and let $m_i=\max(r_i,g_i,b_i)$. If $r_i\geq m_i-1$, we give the color red to $S_i$. Similarly for green and blue.

Does there exist a positive constant $d$ for which we can always color the elements of $S$ in such a way that for any color, at least a fraction $d$ of the sets $S_i$ receive that color?


Yes, you can take at least $d=1/5.$ I suspect the right answer is $1/3,$ which is an upper bound by considering power sets with large $S.$ (More explanation at the end.)

For two colors, red and green, we can start with an all-red coloring. Then as long as less than half the sets receive green, change a red element to green. Before the last change at least half the sets would have been non-green, hence red-only, and they all end up receiving red (and possibly green as well). So the result has at least half the sets receiving red, and at least half the sets receiving green.

For three colors, we start with the red-green coloring constructed above. If at least $k/5$ sets receive blue, we're done. Otherwise, at least $2k/5$ sets are non-blue and satisfy $r_i\geq g_i,$ or more than $2k/5$ sets are non-blue and satisfy $g_i\geq r_i.$ In the first case, change a red element to blue; in the second case change a green element to blue. Repeat this step until at least $k/5$ sets are colored blue. This procedure maintains the invariants $|R\cup B|\geq 2k/5$ and $|G\cup B|\geq 2k/5,$ where $R,G,B$ denote the set of $i$ such that $S_i$ receives red, green, or blue respectively. This is because changing a red element to blue cannot reduce $|G\cup B|.$ And the at least $2k/5$ sets that were non-blue and satisfied $r_i\geq g_i$ will, after changing a red to blue, still satisfy $r_i\geq g_i−1$ and $r_i\geq b_i,$ which leaves them in $R\subseteq R\cup B.$

Without loss of generality, the last change was from red to blue, and the $r_i\geq g_i$ condition ensures there will still be at least $2k/5$ sets receiving red. And at least $k/5$ sets will receive blue, otherwise we would have continued. Before the last step we had $|G\setminus B|=|G\cup B|-|B|>k/5.$ Since the only change was from red to blue, we will still have at least $k/5$ sets receiving green.

Here is an argument for why power sets give a $\tfrac13$ upper bound. Consider a coloring that uses blue least. We will show that at most $\tfrac13+o(1)$ sets receive blue.

Consider a random subset $S_i\subseteq S$ picked uniformly at random. So $b_i\sim B(b,1/2)$ (binomial distribution) where $b$ is the number of blue elements, and similarly for other colors.

If there are less than $n/4$ blue elements, by a Chernoff bound (or central limit theorem) we can see that only $o(1)$ sets receive blue. so we can assume $b\geq n/4.$

Removing a red element from $S$ will only make $r_i$ smaller or equal, so it cannot reduce the fraction of sets receiving blue. And similarly for green. So we can reduce to the case where red, green and blue all receive the same number of elements.

We have $r_i+g_i>n/10$ with probability $1+o(1)$ by the central limit theorem, and conditioned on any particular $r_i+g_i$ greater than $n/10,$ the event $|r_i-g_i|>1$ has probability $1+o(1),$ and similarly for the other pairs of colors. So $S_i$ receives a unique color with probability $1+o(1).$ And conditioned on $S_i$ receiving a unique color, by symmetry it receives blue with probability $\tfrac 1 3.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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