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.


  • 1
    $\begingroup$ 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. $\endgroup$ – user9072 May 9 '12 at 14:00
  • $\begingroup$ 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. $\endgroup$ – Shahab May 9 '12 at 14:58
  • 1
    $\begingroup$ 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 Tressler@gmail.com and I can send you the relevant chapter; I'm not happy enough with my results to post them here as an answer. $\endgroup$ – Eric Tressler May 9 '12 at 16:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Tressler May 9 '12 at 16:54

Your Answer

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

Browse other questions tagged or ask your own question.