Strengthened finite Ramsey theorem

Statement

The strengthened finite Ramsey theorem is a statement about colorings and natural numbers and states that:

For any positive integers n, k, m, such that m ≥ n, one 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.

Without the condition that the number of elements of Y is at least the smallest element of Y, this is a corollary of the finite Ramsey theorem in $K_{\mathcal{P}_n(S)}$, with N given by:

$$\binom{N}{n} = |\mathcal{P}_n(S)| \ge R(\,\underbrace{ m, m, \ldots , m }_k\,).$$

Moreover, the strengthened finite Ramsey theorem can be deduced from the infinite Ramsey theorem in almost exactly the same way that the finite Ramsey theorem can be deduced from it, using a compactness argument (see the article on Ramsey's theorem for details). This proof can be carried out in second-order arithmetic.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic.