# Notation Confusion

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.

-
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 \}. – Zev Chonoles Mar 4 '13 at 2:01
@ZevChonoles Thanks! – 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$.