Rado's theorem (Ramsey theory) (original) (raw)

From Wikipedia, the free encyclopedia

Mathematical result on systems of linear equations

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 A x = 0 {\displaystyle A\mathbf {x} =\mathbf {0} } be a system of linear equations, where A {\displaystyle A} is a matrix with integer entries. This system is said to be r {\displaystyle r} -regular if, for every r {\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 A x = 0 {\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 _C_1, _C_2, ..., C n of the column indices such that if s i = Σ j ∈ C i c j {\displaystyle s_{i}=\Sigma _{j\in C_{i}}c_{j}} , then

1. _s_1 = 0
2. for all i ≥ 2, si can be written as a rational[1] linear combination of the _cj'_s in all the Ck with k < i. This means that si is in the linear subspace of Qm spanned by the set of the cj's.

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

x T = ∑ i ∈ T x { i } , {\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. For proving the former apply Rado's theorem to the matrix ( 1 1 − 1 ) {\displaystyle (1\ 1\ {-1})} . For Van der Waerden's theorem with m chosen to be length of the monochromatic arithmetic progression, one can for example consider the following matrix:

( 1 1 − 1 0 ⋯ 0 0 1 2 0 − 1 ⋯ 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 1 m − 1 0 0 ⋯ − 1 0 1 m 0 0 ⋯ 0 − 1 ) {\displaystyle \left({\begin{matrix}1&1&-1&0&\cdots &0&0\\1&2&0&-1&\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&m-1&0&0&\cdots &-1&0\\1&m&0&0&\cdots &0&-1\end{matrix}}\right)}

Given a system of linear equations it is a priori unclear how to check computationally that it is regular. Fortunately, Rado's theorem provides a criterion which is testable in finite time. Instead of considering colourings (of infinitely many natural numbers), it must be checked that the given matrix satisfies the columns condition. Since the matrix consists only of finitely many columns, this property can be verified in finite time.

However, the subset sum problem can be reduced to the problem of computing the required partition _C_1, _C_2, ..., C n of columns: Given an input set S for the subset sum problem we can write the elements of S in a matrix of shape 1 × |S|. Then the elements of S corresponding to vectors in the partition _C_1 sum to zero. The subset sum problem is NP-complete. Hence, verifying that a system of linear equations is regular is also an NP-complete problem.

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.