$k$ colorings of the non empty subsets of $[n]$ gives the same color to two disjoint sets and their union.

Question

This question was already asked but I didn't get enough information from the answer. Here is a link to the question.

Here is the question restated. Show that for $n$ large enough, every $k$ coloring of the non empty subsets of $[n]$ will give the same color to two disjoint sets and their union.

This is my idea so far. I want to choose $n=R_{k}(3:2)$. Defined to be the smallest $n$ such that any $k$ coloring of the edges of $K_{R_{k}(3:2)}$ yields a monochromatic triangle. Given any k-coloring $f$ on the powerset of $[n]$. Define an edge coloring $f'$ on $K_{n}$ by, $f'(ab)=f(\{a,b\})$.

This produces a monochromatic triangle. So there exists $a,b,c$ such that $\{a,b\},\{b,c\}\{a,c\}$ all have the same color. I was hoping to execute this sort of coloring on the two sets of $[n]$ then the three sets and so on until I have enough triangles to get some disjoint sets but it didn't work.

Any hint would be very nice. Thank you

Answer 1

Define $f'(ab)=f(\{a+1,a+2,\dots,b\})$ for $0\le a\lt b\le n$. This colors the edges of a complete graph on $n+1$ vertices, so you can take $n=R_{k}(3:2)-1$.

Answer 2

Ross's answer in that link gives you a big hint, here is a complete solution.

We prove by induction the existence of a $n_k$, and also get a recurrence relation for some $n_k$ which works.

For $k=2$ we have $n_2=9$ works.

Now, the inductive step:

$P(k)\Rightarrow P(k+1)$.

Define $n_{k+1}=(k+1)(2n_k-1)+1$. By the pigeon hole principle, there are at least $2n_k$ single elements sets which have the same color.

If any of the two corresponding $2$ elements sets have the same color, we are done. Otherwise, the corresponding two elements sets have $k$ colors.

Lets label the elements $x_1,...,x_{2n_k}$. Then we have $n_k$ pairs of elements: $$A_1=\{x_1,x_2 \}, A_2= \{x_2,x_4 \},...., A_{n_k}=\{x_{2n_k-1}, x_{2n_k} \}$$

Now consider all the subsets of $[n_k]$, where a set $S \subset [n_k]$ is colored by the color of $\cup_{j \in S} A_j$.

Apply $P(S)$ and you are done: If $A,B$ are disjoint and $A,B$ and $A \cup B$ are colored with the same color, then

$$\cup_{j \in A} A_j \,;\, \cup_{j \in B} A_j$$ are disjoint and $$\cup_{j \in A} A_j\,;\, \cup_{j \in B} A_j \,;\, \left[\cup_{j \in A} A_j \bigcup \cup_{j \in B} A_j \right]$$ have the same color.

An $n_k$ which works is given by

$$ n_2=9 \,;\, n_{k+1}=(k+1)(2n_k-1)+1 \,.$$

As $$ n_{k+1}=(k+1)(2n_k-1)+1< 2(k+1)n_k \,.$$ you can prove by induction that $$n_k < 9 \cdot 2^{k} \cdot (k!)$$ so $n \geq 9 \cdot 2^{k} \cdot (k!)$ for example works.