The Van der Waerden number W (k, r) denotes the smallest n such that whenever [n] is r–colored there exists a monochromatic arithmetic progression of length k. Similarly, the Hilbert cube number h(k, r) denotes the smallest n such that whenever [n] is r–colored there exists a monochromatic affine k–cube, that is, a set of the form.(forumala presented). We show the following relation between the Hilbert cube number and the Van der Waerden number. Let k > 3 be an integer. Then for every > 0, there is a c > 0 such that Thus we improve upon state of the art lower bounds for h(k; 4) conditional on W(k; 2) being signiffcantly larger than 2k. In the other direction, this shows that if the Hilbert cube number is close to its state of the art lower bounds, then W(k; 2) is at most doubly exponential in k. We also show the optimal result that for any Sidon set A Z, one has (forumala presented).
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics