Chemistry - Rado's Theorem

Rado's Theorem is a theorem from the branch of mathematics known as Ramsey Theory. It is named for the German 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 satifies the columns condition. Let c_i denote the i-th column of A. The matrix A satisfies the columns condition provided that there exists a partition of the column indices C₁, C₂, ..., C_n such if $s_i = \Sigma_{c_j \in C_i}$ , then

s₁ = 0
for all $i \ge 2$ , s_i can be written as a linear combination of the c_j in the C_k with k<i.

Categories: Ramsey theory