This is an extremely soft question.

This is a definition from Ramsey Theory:

$n\to (l_1,\ldots, l_r)^k$ if for every $r$-coloring of $[n]^k$, there exists $i$, $1\le i\le r$, and a set $T$, $|T|=l_i$ so that $[T]^k$ is colored $i$.

I'm confused on the notation of $[n]^k$. In the book it says that for some

$$[X]^k = \{Y:Y\subset X, |Y|=k\}$$

But I still don't really get that if what it means to say that every $r$-coloring of $[n]^k$ yields a monochromatic $[l]^k$. or what raising $[n]$ to the $k$th power does. I understand this definition if we say $[n]$ yields a monochramatic $l$ though.

  • 1
    $\begingroup$ Formatting tip: Stretches of mathematics should all be in the same block of MathJax (and that includes the square braces). You can get curly braces using \{ and \}. $\endgroup$ – Zev Chonoles Mar 4 '13 at 2:01
  • $\begingroup$ @ZevChonoles Thanks! $\endgroup$ – MITjanitor Mar 4 '13 at 2:04

The notation $[X]^k$ indicates the collection of subsets of $X$ of size $k$. Some people write $X^{[k]}$ for this. For example, if $A$ has size $4$, then $[A]^2$ has size $6$, as there are $\binom{4}{2}=6$ ways of picking two elements (i.e., forming a set of size two) out of four. For this reason, some people denote this set by $\binom{X}k$.

Ok. The thing to note is that you are coloring the $k$-sized subsets of $X$, rather than the elements of $X$. For example, if $k=2$, each set of size $2$ can be seen as an edge in a graph with $X$ as set of vertices, so coloring $[X]^2$ is the same as coloring the edges of the complete graph on $X$. For $k=3$, we are coloring "triangles" (not the vertices or the edges, but the "faces"). And so on.

So, to say that $r$-coloring $[X]^k$ results in a monochromatic copy of $[l]^k$ is saying that if the $k$-sized subsets of $X$ are divided into $r$ classes, there is a subset of $X$ of size $l$, all of whose $k$-sized subsets (which, of course, are members of $[X]^k$ as well) are in the same class.

For example, we could take $X=\{1,2,\dots,20\}$, and color a subset $\{a,b,c\}$ of $X$ of size $3$ by the remainder of $a+b+c$ modulo $3$. Some subsets of $X$ of size $4$ are not monochromatic. For example, if $H=\{1,2,3,4\}$, then $\{1,2,3\}$ is colored $0$, while $\{1,2,4\}$ is colored $1$. On the other hand, some subsets of $X$ of size $4$ are monochromatic. For example, if $H=\{3,6,9,12\}$, then any $3$-sized subset of $H$ is colored $0$. Of course, if we change the coloring, then this $H$ may no longer be monochromatic. The assertion $$n\to(l)^k_r$$ is saying that if $X$ has size $n$, then no matter how we $r$-color $[X]^k$, we can find a monochromatic subset of $X$ of size $l$, that is, an $H\subset X$ with $|H|=l$, such that all subsets of $H$ of size $k$ received the same color. The more general $$n\to(l_1,\dots,l_r)^k$$ is saying that if $X$ has size $n$ and we $r$-color $X$, then for some $i$, $1\le i\le r$, there is an $H$ subset of $X$ of size $l_i$, all of whose $k$-sized subsets received color $i$.

  • $\begingroup$ Awesome answer! Thank you! $\endgroup$ – MITjanitor Mar 4 '13 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.