Color each subset of $\{1,2,\ldots,n\}$ either red or blue so that each red number lies in more red subsets than blue subsets...

Question

A positive integer $n > 2$ is chosen, and each of the numbers $1, 2, \dots, n$ is colored red or blue. Show that it is possible to color each subset of $N=\{1,2,\ldots,n\}$ either red or blue so that each red number lies in more red subsets than blue subsets, and each blue number lies in more blue subsets than red subsets.

Attempt of solving

Say element of $N$ is bad, if it lies in at most sets of its color as of the sets pf oposite color.

Randomly color each set $N$. As we have $2^n$ set, we have $2^{2^n}$ different colorings. Take an arbitrary $m$ from $N$, say it is blue and claculate probabilty it is bad. We have $2^{n-1}$ sets with $m$, so we have at least $2^{n-2}$ red set. So some coloring is bad for $m$ if we have

• $0$ blue and $2^{n-1}$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 0} \cdot 2^{2^{n-1}}$$

• $1$ blue and $2^{n-1}-1$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 1} \cdot 2^{2^{n-1}}$$

• $2$ blue and $2^{n-1}-2$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 2} \cdot 2^{2^{n-1}}$$

  $$\vdots $$

• $2^{n-2}$ blue and $2^{n-2}$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 2^{n-2}} \cdot 2^{2^{n-1}}$$

So the number of all bad colorings for $m$ is $$ \sum _{i=0}^{2^{n-2}}{2^{n-1}\choose i} \cdot 2^{2^{n-1}} = {1\over 2} \Big(2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \Big)\cdot 2^{2^{n-1}}$$ so the probability $m$ is bad is: $$P = {2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \over 2\cdot 2^{2^{n-1}}}$$ So the probability that at least one elements is bad in bounded by : $$n\cdot {2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \over 2\cdot 2^{2^{n-1}}}$$ which is clearly more than 1 so the union bound does not apply here.

I was wondering if Lovasz local lemma can be aplied here? Any help?

Answer 1

You shouldn't expect a naive application of the local lemma to work, because:

• In a uniformly random coloring, the probability that a number is contained in more red sets than blue sets is a constant: approximately $\frac12$.
• However, the number of dependencies is not constant: it grows exponentially with $n$.

In fact, the high probability of failure is an obstacle with any probabilistic coloring method.

---

A deterministic coloring works. Suppose $R$ is the set of red elements and $B$ is the set of blue elements. Begin by coloring a set $S$ red if $|R \cap S| > \frac12|R|$, and blue otherwise. The quality of the result depends on the parity of $r := |R|$.

• When $r$ is odd, red elements are ahead by $\binom{r-1}{(r-1)/2}2^{n-r}$ of the sets containing them, and blue elements have an equal number of red and blue sets that contain them.
• When $r$ is even, red elements have an equal number of red and blue sets that contain them, and blue elements are ahead by $\binom{r}{r/2}2^{n-r}$ of the sets containing them.

Ties are bad, so in either case, we'll have to fix the coloring slightly. When $r$ is odd (and $r \ne n$, so blue elements exist), boost blue elements by $1$ by coloring the set $\{1, 2, \dots, n\}$ blue instead of red.

When $r$ is even, or if the previous step brought the red elements down to an even split (which happens for instance if $r=1$ and $n=2$), boost red elements by $1$ by coloring each singleton set $\{x\}$ for $x \in R$ red, instead of blue. This is a free action: it doesn't hurt blue elements at all, but gives red elements the boost they needed.