Deriving Van der Waerden's theorem from Rado's theorem

343 Views Asked by At

In Ramsey Theory Van der Waerden theorem states that,

Let $k,r$ be positive integers. Then in every partitioning of the positive integers into $r$ classes there is one class which contains an arithmetic progression of length $k$.

This was proved by Van der Waerden in 1927.

Rado's theorem proved in 1933 states:

Let $A=\begin{pmatrix} \vec{c_1}&\vec{c_2}&\cdots \vec{c_n} \end{pmatrix}$ be an $m\times n$ matrix with integer entries and $r$ be a positive integer. Call the system of linear equations $Ax=0$ $r$-regular if every partitioning of the natural numbers into $r$ classes is such that one of classes contains a solution of this system. Call this system regular if it is $r$-regular for all $r\ge > 1$. Then $Ax=0$ is regular if and only if there exists a positive integer $k$ and a partition $C_1,C_2,\cdots,C_k$ of the column vectors of $A$ such that $\displaystyle\sum_{\vec{c_i}\in C_1}\vec{c_i}=0$ and for all $j>1$ the vector $\displaystyle\sum_{\vec{c_i}\in > C_j}\vec{c_i}$ is a rational linear combination of the column vectors from $C_1,\cdots,C_{j-1}$.

My question is, is it possible to derive Van der Waerden's theorem from Rado's theorem by choosing an appropriate $A$?

1

There are 1 best solutions below

0
On BEST ANSWER

$A=\begin{pmatrix} 1&-1& & &&1\\ &1 &-1 & &&1\\ & &1 &-1 &&1\\ & & &\ddots\\ & & &1 &-1 &1 \end{pmatrix}_{(k-1)\times(k+1)}$