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 reading wikipedia article about Paris-Harrington theorem, which uses strengthened finite Ramsey theorem, which is stated as "For any positive integers $n, k, m$ we can find $N$ with the following property: if we color each of the $n$-element subsets of $S = \{1, 2, 3,..., N\}$ with one of $k$ colors, then we can find a subset $Y$ of $S$ with at least $m$ elements, such that all $n$ element subsets of $Y$ have the same color, and the number of elements of $Y$ is at least the smallest element of $Y$".

After poking around for a while I interpreted this as follows.

Let $n,k$ and $m$ be positive integers. Let $S(N)=\{1,...,N\}$ and $S^{(n)}(M)$ be the set of $n$-element subsets of $S(M)$. Let $f:S^{(n)}(M)\to \{1,...,k\}$ be some $k$-colouring of $S^{(n)}(M)$. Theorem states that for any $n, k, m$ there is a number $N$ for which we can find $Y\subseteq S(N)$ such that $|Y|\geq m$, the induced colouring $f':Y^{(n)}\to \{0,...,k\}$ boils down to a constant function (every $n$-subset of $Y$ has the same colour) and $|Y|\geq\min{Y}$.

In this correct?

I also faced another formulation where it is stated that "for any $m,n,c$ there exists a number $N$ such that for every colouring $f$ of $m$-subsets of $\{0,...,N-1\}$ into $c$ colours there is an $f$-homogeneous $H\subset\{0,..,N-1\}$...".

How $f$-homogeneous is defined?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Yes, your interpretation of the first formulation is correct.

In the second formulation the statement that $H$ is $f$-homogeneous simply means that every $m$-subset of $H$ is given the same color by $f$: in your notation, the induced coloring $$f\,':H^{(m)}\to\{0,\dots,c-1\}$$ is constant. However, the formulation is missing the important requirement that $|H|\ge\min H$.

share|improve this answer
Great, thank you. –  rank Mar 1 '12 at 14:46

Your Answer


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.