Some new bounds and values for van der Waerden-like numbers (Q807624): Difference between revisions

Consider increasing sequences of positive integers \(\{x_ 1,x_ 2,...,x_ n\}\) that either form an arithmetic progression or for which there exists a polynomial f with integer coefficients and degree exactly n-2, and \(x_{j+1}=f(x_ j)\). Denote by q(n,k) the least positive integer such that if \(\{\) 1,2,...,q(n,k)\(\}\) is partitioned into k classes, then some class must contain a sequence of the above type. q(n,k) is analogous to the well-known van der Waerden number w(n,k), i,e. the least positive integer which guarantees that if \(\{\) 1,2,...,w(n,k)\(\}\) is partitioned into k sets, then at least one of the k sets contains an arithmetic progression of length n. In [the authors: On the existence of a reasonable upper bound for the van der Waerden numbers, J. Comb. Theory (A), to appear] they proved that \(q(n,2)\leq (n!)^{(n-2)!/2}\) for \(n\geq 4\). In this paper they obtain upper bounds for q(n,3), q(n,4), q(3,k), and q(4,k). Moreover, by using an algorithm similar to that of [the authors: Values and bounds for Ramsey numbers associated with polynomial iteration, Discrete Math. 68, 77-83 (1988; Zbl 0632.05010)], they have found several values of q(n,k).