On semi-progression van der Waerden numbers
- PDF / 227,448 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 186 Views
On semi-progression van der Waerden numbers Zehui Shao · Xiaodong Xu
Received: 5 September 2011 / Revised: 9 October 2012 / Accepted: 30 November 2012 / Published online: 28 March 2013 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2013
Abstract In this note, a dynamic programming-like method is used to detect k-term semiprogression efficiently. By using this approach, we obtain some exact values and new lower bounds on semi-progression van der Waerden numbers. Keywords Arithmetic progression · Szemeredi’s ´ theorem · Dynamic programming · Semi-progression Mathematics Subject Classification
Primary 05D10; Secondary 05D05
1 Introduction Let k ≥ 2, a k-term arithmetic progression, also called a k-AP, is a sequence of positive integers {a1 , a2 , · · · , ak } such that there is a constant positive integer d with the property that ai+1 − ai = d for i = 1, 2, · · · , k − 1. For integers a ≤ b, we denote by [a, b] the interval {r |a ≤ r ≤ b} of integers between a and b. For integers a and b = 0, we write b| a if a is dividable by b.
Communicated by Alagacone Sri Ranga. Z. Shao (B) School of Information Science and Technology, Chengdu University, Chengdu 610106, China e-mail: [email protected] Z. Shao Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu, China X. Xu Guangxi Academy of Sciences, Nanning 530007, China e-mail: [email protected]
123
20
Z. Shao, X. Xu
We firstly recall a famous Ramsey-type theorem on the integers, van der Waerden’s theorem Graham et al (1990); Landman and Robertson (2004), the following: Theorem 1 Let k, r ≥ 2 be integers. There exists a least positive integer w = W (k; r ) such that for all n ≥ w, for every r -coloring of [1, n] there is a monochromatic arithmetic progression of length k. The numbers W (k; r ) are called van der Waerden numbers. The mixed van der Waerden number W (k1 , k2 , · · · , kr ; r ) is the smallest integer w such that every r -coloring of [1, w] contains a monochromatic ki -term arithmetic progression with color i for some i. Let us look at the related definitions of semi-progression van der Waerden number from Landman and Robertson (2004). Definition 1 For positive integers m and k, a k-term semi-progression of scope m is a sequence of positive integers {x1 , x2 , · · · , xk } such that , for some d > 0, xi − xi−1 ∈ {d, 2d, · · · , md} for all 2 ≤ i ≤ k. It is easy to see that when m = 1, the k-term semi-progression is the classical arithmetic progression. Definition 2 The semi-progression van der Waerden number SW (k1 , k2 , · · · , kr ; r ; m) is the smallest integer w such that every r -coloring of {1, 2, · · · , w} contains a monochromatic ki -term semi-progression of scope m with color i for some i. When k1 = k2 = · · · = kr = k, SW (k1 , k2 , · · · , kr ; r ; m) is written as S Pm (k; r ); When r = 2, S Pm (k; r ) is written as S Pm (k). Definition 3 For positive integers r, m, k1 , k2 , · · · , kr , a coloring is said to be a (k1 k2 , · · · ,
Data Loading...
