what is the generalization of this problem

85 Views Asked by At

$\text{Statement}$:

In any partition of $X=(1,2,3,..9)$ into $2$ subsets, at least one of the sets contains an arithmetic progression of length $3$.

Can this problem be generalized?

In any partition of $X=(1,2,3,..a)$ into $2$ subsets, at least one of the sets contains an arithmetic progression of length $b$.

In simpler words, what is the relation between $a$ and $b$?

1

There are 1 best solutions below

0
On

Short answer: Nobody really knows. This is an open research area. As Gowers 2001 says, “this has turned out to be a surprisingly difficult question”.


Van der Waerden's theorem states that for every $b$ there is a number $W(b;2)$ such that when $a\ge W(b;2)$ your property (“any partition … progression of length $b$”) holds, and provides an upper bound for $W(b;2)$.

However, no good upper bounds are known; the one given by van der Waerden's proof itself is ridiculously large. (For the $b=3$ case, it gives the bound $W(3;2)\le 325$, where as you know the correct answer is $9$. The bounds obtained for $b>3$ are vastly sillier.)

I believe the current state of the art is $$\left(\frac{2^n}{2ne}\right)(1 + o(1))\le W(b;2) \le 2^{2^{2^{2^{2^{b+9}}}}} $$ (The lower bound due to Graham et al 1987 and the upper bound to Gowers 2001). Wikipedia also says that the lower bound has been slightly improved by Z. Szabó.

A few specific values of $W()$ are known:

$$\begin{array}{cr} b & W(b; 2) \\\hline 1 & 1 \\ 2 & 3 \\ 3 & 9 \\ 4 & 35 \\ 5 & 178 \\ 6 & 1132 \end{array}$$

(Kouril and Paul 2008) No other exact values for $W(b;2)$ are known.

The Wikipedia article on “Van der Waerden numbers” provides more detail.