Let $$ \Lambda = \{(x,y)\in\mathbb{N}^2:y\geq x\} $$ the upper triangular lattice and $d:\Lambda\to\{1,\dots,c\}$ a coloring (i.e. an arbitrary function) on $c$ colors. Let $k\geq2$. I am looking for $n\in \mathbb{N}$, $m_1<m_2<\dots m_k$ and $n_j \in [n,m_j]\cap\mathbb{N}$, $j=2,\dots,k$, such that the set $$ B = \{(n,m_1),(n,m_2),\dots,(n,m_k), (n_2,m_2),(n_3,m_3),\dots,(n_k,m_k)\}$$ is monochromatic (i.e. all its points have the same color). See the picture below for an example.

From the ergodic proof of multidimensional Van der Waerden theorem it is easy to show that such set $B$ always exists; moreover, one also has $$ s(B) := \max_{1\leq j\leq k}m_j-n_j \leq m_1$$ My question is: can I take $B$ such that $s(B)$ is bounded by something depending only on the number of colors $c$?

  • $\begingroup$ It looks so. You may simply find this pattern in $N$ lower rows where $N$ depends only on $c$. Also usual 2-dimensional van der Waerden is pretty enough: your set contains large grid of size about $N/2$ where you may find anything you need. $\endgroup$ – Fedor Petrov Dec 10 '19 at 1:37

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.