Ramsey Functions Associated with Second Order Recurrences

Abstract

Numbers similar to the van der Waerden numbers $w(n)$ are studied, where the class of arithmetic progressions is replaced by certain larger classes. If ${\mathcal{A}}^{\prime }$ is such a larger class, we define $w^{\prime }(n)$ to be the least positive integer such that every $2$-coloring of $\{1,2,\dots ,w^{\prime }(n)\}$ will contain a monochromatic member of ${\mathcal{A}}^{\prime }$. We consider sequences of positive integers $\{x_1,\dots ,x_n\}$ which satisfy $x_i=a_i{x}_{i-1}+b_i{x}_{i-2}$ for $i=3,\dots ,n$ with various restrictions placed on the $a_i$ and $b_i$. Upper bounds are given for the corresponding functions $w^{\prime }(n)$. Further, it is shown that the existence of somewhat stronger bounds on $w^{\prime }(n)$ would imply certain bounds for $w(n)$.