Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on some Combinatorics, and in the past have happily used the infinite Ramsey Theorem (as detailed on http://en.wikipedia.org/wiki/Ramsey%27s_theorem), which says that for something like $\mathbb{N}$, given any finite colouring of the size-$n$ subsets of $\mathbb{N}$ (for n fixed), there exists an infinite subset M with all size-$n$ subsets of M monochromatic. I only need the existence of arbitrarily large such M here, not infinite.

However, I'm trying to work my way through the following paper: http://www.mendeley.com/research/transfinite-approximation-hindmans-theorem/# (I seem to be able to preview the first 15 pages for free, hopefully you can too) and having reached the end of the third page, there is a proof about monochromatic finite unions of disjoint sets (the 'power-set version of Folkman's theorem', informally), which appears to use the result that we can always find a (finite) set of arbitrarily large size for which all finite subsets are monochromatic with colour depending only on their cardinality. (In the above paper this set is denoted 'Y'.)

So, essentially this is saying we can find an arbitrarily large subset M for which Ramsey's theorem applies for all size-$n$ subsets of M for every single $n$, $1 \leq n \leq |M|$, simultaneously, just with colours varying across different n. However, I can't seem to find any documentation of this following from Ramsey's theorem, and it is not obvious to me that given the theorem in my first paragraph, we can easily deduce such a subset exists which works for all these different $n$ simultaneously. A number of sources I've seen just call this result 'Ramsey's Theorem' however (including the above paper), so I presume it must follow reasonably easy from the fixed-$n$ case; could someone please enlighten me as to how we get to this 'extended Ramsey's Theorem'? Many thanks - Ben

share|improve this question
1  
I got an error from that link, but if it’s this paper, it’s freely available in its entirety. –  Brian M. Scott Nov 23 '11 at 4:58
add comment

1 Answer

up vote 0 down vote accepted

I’m assuming that you’re looking at this sentence:

Pick, using Ramsey’s Theorem, an integer $m$ such that for any $r$-coloring of $\wp(X)$, where $|X| = m$, there exists a set $Y \subseteq X$, $|Y| = l$ with the color of the subsets of $Y$ depending solely on their cardinality.

Let $R(n;r,k)$ be such that if $m\ge R(n;r,k)$, and the $k$-subsets of $[m]$ are $r$-colored, then there is an $n$-subset of $[m]$ whose $k$-subsets are all the same color; the existence of $R(n;r,k)$ is the content of the ordinary finite Ramsey theorem. Let $m_1=R(l;r,1)$, and for $k=2,\dots,l$ let $m_k=R(m_{k-1};r,k)$.

Suppose that $m\ge m_l$, and the subsets of $[m]$ are $r$-colored. Then there is a $Y_l\subseteq [m]$ such that $|Y_l|\ge m_{l-1}$, and the $l$-subsets of $Y_l$ are all the same color. By the definition of $m_{l-1}$, there is a $Y_{l-1}\subseteq Y_l$ such that $|Y_{l-1}|\ge m_{l-2}$, and the $(l-1)$-subsets of $Y_{l-1}$ are all the same color. Note that since $Y_{l-1}\subseteq Y_l$, the $l$-subsets of $Y_{l-1}$ are still monochromatic. By an easy finite induction we get $Y_2\subseteq Y_3\subseteq\dots\subseteq Y_l\subseteq[m]$ such that $|Y_2|\ge m_1$, and for each $k=2,\dots,l$ the $k$-subsets of $Y_2$ are monochromatic. Finally, there is a $Y\subseteq Y_2$ such that $|Y|\ge l$ and the singletons of $Y$ are monochromatic, and since $Y\subseteq Y_k$ for $k=2,\dots,l$, the $k$-subsets of $Y$ are monochromatic for $k=1,\dots,l$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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