Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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