2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.