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.

What is the maximum 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?

An algorithm that starts with a two-coloring and change the color of one element at a time to the third color achieves $d=1/5$, while an example shows that $d=1/3$ is the best one can hope for.

  • $\begingroup$ Looks like you are quite desperate to get an answer: you asked the question just two days ago and already put a bounty on it :lol: Let people think a bit ;-). I'm betting on 1/3 with some stupid algorithm of the sort "keep three balls in the bank, award one to the color that cannot get rich from that (i.e. would not get a true maximum in $\ge k/3$ sets) and then take one ball from a rich color to fill the bank. If no such award is possible, distribute the bank in any way and you are done". Unfortunately, I cannot prove termination and am not even sure if no extra twists are needed. $\endgroup$ – fedja Nov 21 '17 at 21:37
  • $\begingroup$ Why 3 colors, what happens for 2? Why $r_i\ge m_i-1$, what happens for $r_i\ge m_i$? $\endgroup$ – domotorp Nov 22 '17 at 8:02
  • 1
    $\begingroup$ @domotorp Both of those cases are easy. For 2 the optimal d is 1/2. For $r_i\geq m_i$ it is 0 (e.g. n=1). $\endgroup$ – Karo Nov 22 '17 at 9:36
  • $\begingroup$ Are you familiar with the methods used e.g. in this paper? arxiv.org/abs/1704.02921 $\endgroup$ – domotorp Nov 22 '17 at 10:19

The statement seems to follow from Sperner's lemma. We will give such a coloring that the first few elements are red, the middle ones are green and the last few are blue (for any ordering of the elements).

We can represent the colorings of the $n$ elements with a subdivision of a large triangle into $n^2$ smaller triangles in the standard way, where the side lengths of the small triangles are $1$, while the side lengths of the large triangle are $n$. Express the vertices of the small triangles using barycentric coordinates. All barycentric coordinates will be of the form $\frac{r_v}n,\frac{g_v}n,\frac{b_v}n$, where $r_v$, $g_v$ and $b_v$ are non-negative integers. To each vertex $v$, assign a coloring of the elements, $C(v)$, where $r_v$, $g_v$ and $b_v$ elements are red, green and blue, respectively.

Now we define the colors of the vertices (which will be used in Sperner's lemma). A vertex $v$ is colored red if in $C(v)$ for at least $k/3$ sets we have that $r_i\ge m_i$. (Attention, there is no $-1$!) A vertex is colored green if it is not red, and in $C(v)$ for at least $k/3$ sets we have that $g_i\ge m_i$. A vertex is colored blue if it is not red or green, and in $C(v)$ for at least $k/3$ sets we have that $b_i\ge m_i$. Note that every vertex gets colored and the coloring satisfies the conditions of Sperner's lemma. Therefore, we get a $3$-colored small triangle. But it is easy to see that any of its vertices will give a coloring $C(v)$ that satisfies the required conditions.

Update: Oops, as pointed out by Dap, the "easy to see part" is incorrect (as usual ;). One possible fix is to use real coordinates, as described by fedja. Another would be to allow multiple colors for each vertex, i.e., the "if it is not red" type conditions should be ignored. For such a multicoloring, Sperner's lemma is still true, and we get a triangle whose vertices contain all 3 colors (some possibly multiple times). And now the "easy to see" part should work because the "danger sets", i.e., the ones for which we have, e.g., $m_i=r_i=g_i$, contribute to multiple color counts, like in this case to both $r_i$ and $g_i$. But I don't see how to finish this workaround without a cumbersome calculation.

  • 2
    $\begingroup$ In the last step, it's not clear to me why any vertex of the small triangle satisfies the conditions. Suppose we have a triangle with vertices $(r+1,g,b),(r,g+1,b),(r,g,b+1)$ (ignoring the $1/n$ scaling), colored red, green and blue respectively. Why should the red vertex have at least a third of sets receiving green? Compared to the green vertex, one green element has changed to red, which can decrease $g_i$ and increase $m_i,$ so sets that had $g_i\geq m_i$ are only guaranteed to satisfy $g_i\geq m_i-2.$ $\endgroup$ – Dap Nov 23 '17 at 6:06
  • 2
    $\begingroup$ @Dap That is a valid objection, of course, but the fix is easy. Let us just allow ourselves real coordinates (some balls can be shared when the dividing bars move through them). Then we have a triple real point $(x,y,z)$ with the sum $n$. Notice that we can move the bars to the nearest integers changing two numbers by $\le\frac 12$ and the third number by at most $1$, so the sum of any two changes will be below $3/2$. Thus, we will have the inequalities $r_i\ge m_i-3/2$, which automatically improve to $-1$ since everything is an integer now. Beautiful solution, Domotorp! $\endgroup$ – fedja Nov 23 '17 at 6:50
  • $\begingroup$ @fedja Your fix is not very clear to me - how do you choose the triple real point $(x,y,z)$? Are you still using Sperner's lemma? $\endgroup$ – Karo Nov 23 '17 at 9:47
  • $\begingroup$ @Karo I think fedja is using some continuous version of it, like en.wikipedia.org/wiki/…. $\endgroup$ – domotorp Nov 23 '17 at 10:05
  • $\begingroup$ @Karo Also, if you do not like the continuous version, it is enough to use the discrete mesh with step $1/5$, say, because $\frac 25+\frac 32<2$ $\endgroup$ – fedja Nov 23 '17 at 14:12

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.