Extremal problems for affine cubes of integers. (English) Zbl 0892.05050

Gunderson, David S.; Rödl, Vojtěch

Comb. Probab. Comput. 7, No. 1, 65-79 (1998).

A collection \(H\) of integers is called an affine \(d\)-cube if there exist \(d+1\) positive integers \(x_0,x_1, \dots, x_d\) so that \[ H= \Bigl\{x_0+ \sum_{i\in I}x_i: I\subseteq \{1, \dots, d\}\Bigr\}. \] The following theorem is proved: Let \(d\geq 3\) and \(A\subseteq \{1,\dots,n\}\) be given. Then there exists \(n_0\leq 2^{d2^{d-1}/(2^{d-1} -1)-1}\) so that, for every \(n\geq n_0\), \(A\) contains an affine \(n\)-cube, if \[ | A| \geq 2^{1-1/2^{d-1}} (\sqrt n+1)^{2 -1/2^{d-2}}. \] Let \(h(d,r)\) be the least number so that, for any \(r\)-colouring of \(\{1, \dots,n\}\), there is a monochromatic affine \(d\)-cube. It is shown that for \(d\geq 3\) and \(r\geq 2\) \[ r^{\bigl(1-o(1) \bigr) (2^d-1)/d} \leq h(d,r) \leq(2r)^{2^{d-1}}, \] where \(o(1)\to 0\) as \(r\to\infty\).

Reviewer: K.Engel (Rostock)

MSC:

05D10	Ramsey theory
05C55	Generalized Ramsey theory

Keywords:

van der Waerden theorem; Schur theorem; density; partition; Ramsey number; affine \(d\)-cube