Ramsey Theory on subsets of $\{1, 2, \dots, n\}$, $k$ colored.

252 Views Asked by At

Prove that there exists a $n$ natural for each $k > 0$ natural such that, by coloring all the subsets of $\{1, 2, \dots, n\}$ with $k$ colors, there exist two disjoint subsets among them, $X$ and $Y$, such that $X, Y, X \cup Y$ are identically colored.

I am aware of Schur's theorem, which has a relatively similar statement, but it is actually for numbers in a set with their sum, while this problem is for sets in a 'family' with their union. I'm thinking to create a bijective indicator, that transforms each of the elements of $S \in \mathcal{P(n)}$ into a natural number $\omega(S)$, indicator function that also have the property that for distinct sets: $$\omega(A) + \omega(B) = \omega(A \cup B)$$

Actually, If I proved this, I would have solved the problem since Schur's theorem may be used. However, I couldn't find a proof for this fact on a general case.

For example, a valid (satisfies the definition conditions, but does not form a correct Schur-type set) function for $n = 3$ would be: $\omega(\emptyset) = 0$, $\omega(\{1\}) = 1$, $\omega(\{2\}) = 3$, $\omega(\{3\}) = 5$, $\omega(\{1, 2\}) = 4$, $\omega(\{1, 3\}) = 6$, $\omega(\{2, 3\}) = 8$ and $\omega(\{1, 2, 3\}) = 9$.

1

There are 1 best solutions below

0
On BEST ANSWER

This theorem does have a proof based on Schur's theorem, but we would also have to invoke a version of the hypergraph Ramsey's theorem.

Let $S(k)$ be the least number such that if $\{1, 2, \dots, S(k)\}$ are $k$-colored, there is a monochromatic sum $a+b=c$ (with $a,b$ not necessarily distinct).

Let $n$ be large enough that in any coloring of $\mathcal P(n)$, there is a subset $D$ of size $S(k)$ such that the color of every $i$-element subset of $D$ is the same (possibly depending on $i$). This gives us a coloring of $\{1, 2, \dots, S(k)\}$ by giving each value $i$ the color of an $i$-element subset of $D$. Now within that coloring, find a monochromatic sum $a+b=c$; we are done by choosing disjoint $A,B \subseteq D$ with $|A|=a$ and $|B|=b$.

This is massive overkill, but has the advantage that it generalizes to using Folkman's theorem (an analog of Schur's theorem which finds a larger set such that the sum of any nonempty subset is the same color) to prove the finite unions theorem (the same, but for a collection of disjoint sets, with $\cup$ instead of $+$).

It does not seem that there is an easy direct argument that uses Schur's theorem to find a monochromatic disjoint union. (There sure is one in reverse, though!)


However, there is a shorter proof using Ramsey's theorem for triangles, which is completely analogous to the proof of Schur's theorem using the same result.

Starting from a coloring of $\mathcal P(n)$, take a complete graph with vertices $v_0, v_1, v_2, \dots, v_n$, and give each edge $v_i v_j$ (assuming $i<j$) the color of the set $\{i+1, i+2, \dots, j\}$. Then the three edges of a monochromatic triangle form a triple $A, B, A\cup B$ in which the two smaller sets are disjoint.