Some new bounds and values for van der Waerden-like numbers
type: Item
instance of: scholarly article
title: Some new bounds and values for van der Waerden-like numbers
zbMATH Open document ID: 0731.05006
DOI: 10.1007/BF01787579
author: Raymond N. Greenwell
author: Bruce M. Landman
published in: Graphs and Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: 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).
reviewed by: Jiahai Kan
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 4208081
zbMATH Keywords: polynomial iteration
zbMATH Keywords: arithmetic progression
zbMATH Keywords: van der Waerden number
MaRDI profile type: Publication
cites work: A Construction for Partitions Which Avoid Long Arithmetic Progressions
cites work: A Short Proof of van der Waerden's Theorem on Arithmetic Progressions
cites work: On the existence of a reasonable upper bound for the van der Waerden numbers
cites work: Generalized van der Waerden numbers
cites work: Values and bounds for Ramsey numbers associated with polynomial iteration
cites work: Primitive Recursive Bounds for Van Der Waerden Numbers
cites work: Q5650404
full work available at URL: https://doi.org/10.1007/bf01787579
OpenAlex ID: W2076721162
Recommended article: On the existence of a reasonable upper bound for the van der Waerden numbers
Recommended article: An application of Lovász' local lemma-A new lower bound for the van der Waerden number
Recommended article: Generalized van der Waerden numbers
Recommended article: On computation of exact van der Waerden numbers
Recommended article: Two New Van Der Waerden Numbers: w(2; 3, 17) and w(2; 3, 18)
Recommended article: Some new van der Waerden numbers and some van der Waerden-type numbers
Recommended article: On sets without \(k\)-term arithmetic progression
Recommended article: A subexponential upper bound for van der Waerden numbers \(W(3,k)\)
Recommended article: Q4304347
description: scientific article; zbMATH DE number 4208081