Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Alon Amit
Alon Amit
  • 6.7k
  • 3
  • 53
  • 83

The strengthened finite Ramsey theorem:

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.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic. See the Wikipedia article on the Paris-HuntingtonHarrington theorem.

The strengthened finite Ramsey theorem:

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.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic. See the Wikipedia article on the Paris-Huntington theorem.

The strengthened finite Ramsey theorem:

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.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic. See the Wikipedia article on the Paris-Harrington theorem.

Source Link
Kristal Cantwell
Kristal Cantwell
  • 6.5k
  • 1
  • 25
  • 45

The strengthened finite Ramsey theorem:

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.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic. See the Wikipedia article on the Paris-Huntington theorem.