Fraction of the sets receive each color

Question

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.

Answer 1

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.