Rado's theorem (Ramsey theory)

From Wikipedia, the free encyclopedia

There is also a Rado's theorem about harmonic functions.

Rado's theorem is a theorem from the branch of mathematics known as Ramsey theory. It is named for the English mathematician Richard Rado.

Let Ax=0 be a system of linear equations, where A is a matrix with integer entries. This system is said to be r-regular if, for every r-coloring of the natural numbers 1, 2, 3, ..., the system has a monochromatic solution. A system is regular if it is r-regular for all r \ge 1

Rado's theorem states that a system Ax=0 is regular if and only if the matrix A satisfies the columns condition. Let ci denote the i-th column of A. The matrix A satisfies the columns condition provided that there exists a partition of the column indices C1, C2, ..., Cn such if s_i = \Sigma_{j \in C_i}c_j, then

  1. s1 = 0
  2. for all i \ge 2, si can be written as a linear combination of the cj's in the Ck with k<i.
Retrieved from "http://en.wikipedia.org../../../r/a/d/Rado%27s_theorem_%28Ramsey_theory%29_fb4c.html"