MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to develop bounds for the function B(k) where B(k) is defined as the least such positive integer so that whenever the set $\{1,2,\cdots B(k)\}$ is partitioned into two parts at least one part contains a set of order k, $\{x_1 < x_2 < \cdots x_k\}$, where the differences $x_i-x_{i-1}\in \{ a,b \}$ for some $a,b\in \mathbb{Z}^+$. Clearly $B_k$ exists since the van der Waerden theorem guarantees its existence.

What I am specifically interested to know is to whether someone has tackled this problem before and what results have been obtained in that connection.


share|cite|improve this question
The book by Landman and Robertson "Ramsey Theory on the Integers" is a good general reference for this type of problems. Not sure, and unable to check, if it contains anything on the specific question though. – user9072 May 9 '12 at 14:00
I have that book and the problem is taken from there. However the references mentioned there don't contain any results about this specific problem but are about related problems. – Shahab May 9 '12 at 14:58
This was exactly the topic of one of the chapters of my thesis, though I did not fix the number of differences at 2. Interestingly, if we define B_m(k,r) to be analogous to the VDW numbers, but with m differences, length k progressions, and r colors, then B_2(4,2) = 9, B_2(4,3) = 16, B_2(4,4) = 25, and B_2(4,5) = 37... The Szemeredi cube lemma gives some trivial bounds here. Email me at and I can send you the relevant chapter; I'm not happy enough with my results to post them here as an answer. – Eric Tressler May 9 '12 at 16:49
Also, more relevant to your actual question, we have B_2(n,2) = 9,14,21,28,41,53 for n=4,5,6,7,8,9 respectively. Since the lower bound for VDW numbers is exponential, it would be interesting to know if these numbers have the same property; I wasn't able to prove it. – Eric Tressler May 9 '12 at 16:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.