# Rado's theorem (Ramsey theory)

Jump to navigation Jump to search

Rado's theorem is a theorem from the branch of mathematics known as Ramsey theory. It is named for the German mathematician Richard Rado. It was proved in his thesis, Studien zur Kombinatorik.

Let ${\displaystyle A\mathbf {x} =\mathbf {0} }$ be a system of linear equations, where ${\displaystyle A}$ is a matrix with integer entries. This system is said to be ${\displaystyle r}$-regular if, for every ${\displaystyle 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 ≥ 1.

Rado's theorem states that a system ${\displaystyle A\mathbf {x} =\mathbf {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 C1, C2, ..., Cn of the column indices such that if ${\displaystyle s_{i}=\Sigma _{j\in C_{i}}c_{j}}$, then

1. s1 = 0
2. for all i ≥ 2, si can be written as a rational[1] linear combination of the cj's in the Ck with k < i.

Folkman's theorem, the statement that there exist arbitrarily large sets of integers all of whose nonempty sums are monochromatic, may be seen as a special case of Rado's theorem concerning the regularity of the system of equations

${\displaystyle x_{T}=\sum _{i\in T}x_{\{i\}},}$

where T ranges over each nonempty subset of the set {1, 2, ..., x}.[2]

Other special cases of Rado's theorem are Schur's theorem and Van der Waerden's theorem.

## References

1. ^ Modern graph theory by Béla Bollobás. 1st ed. 1998. ISBN 978-0-387-98488-9. Page 204
2. ^ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), "3.4 Finite Sums and Finite Unions (Folkman's Theorem)", Ramsey Theory, Wiley-Interscience, pp. 65–69.