$X$ a finite set and $A_1,A_2,...,A_r$ be subsets of $X$ of size $m$. If $r < 2^{m-1}$, then $\exists$ a $2$-coloring of $X$ s.t. no $A_i$ is mono.

Question

Monochromatic. I want to find a non-probabilistic proof of this statement, because I already know a probabilistic one. The probabilistic proof basically uses the fact that $P(Y \leq E[Y])>0$ for a random variable $Y$. We color the elements of $X$ uniformly and get that the expected number of monochromatic subsets is $1$...

Answer 1

The natural argument to make here is probabilistic, so you may or may not think of these alternatives as "thin disguises":

Proof 1. There are $2^{|X|}$ colorings of $X$. For each $i$, there are $2^{|X|-m+1}$ "bad" colorings where $A_i$ is monochromatic. Altogether, the number of bad colorings is at most $r \cdot 2^{|X|-m+1}$, which is less than $2^{|X|}$, so some "good" colorings must also exist.

Proof 2. We will color the elements of $X$ one at a time, and assign each set $A_i$ a danger level that we update as we go. Initially, each $A_i$ has danger level $1$. Whenever an element of $A_i$ is colored:

• If $A_i$ now has elements of both colors, its danger level is permanently set to $0$.
• If the newly colored element is the first element of $A_i$ we colored, its danger level is unchanged.
• If $A_i$ already had elements of the color we used just now (and no elements of the other color), its danger level doubles.

Whenever we color $x \in X$, some of the $A_i$'s might double in danger level and others will have their danger level set to $0$. If we change the color we use on $x$, that exactly swaps which danger levels double and which danger levels get set to $0$. Therefore whatever the two possible total changes in danger level are when we color $x$, they are equal and opposite in sign.

We choose our colors so that at every step, the total danger level does not increase. Initially, the total danger level is equal to $r$, so at the end it is at most $r$. This means that we cannot end with a monochromatic $A_i$: such an $A_i$ would have a danger level of $2^{m-1} > r$ all on its own, since its danger level would have doubled $m-1$ times.