## Abstract

For each positive integer n, G(n) is defined to be the largest integer k such that no matter how Z_{n} is two-colored, some progression a, a + d, a + 2d, ..., a + (k - 1)d of k distinct elements of Z_{n} will appear in one color. Our main theorem shows constructively that if Z_{n} can be two-colored in such a way that the longest monochrome progression has m distinct terms mod n and any monochrome progression of k distinct terms with common difference d ≢ 0 (mod n) has the property that kd ≢ 0 (mod n), then G(rn) ≤ m for 1 ≤ r ≤ m and G(rn) ≤ r for r > m. One lower bound on G(n) says G(rn) ≥ G(n) for r ≥ 1 and n ≥ 1. Two main results with corollaries, a "quadratic-residue coloration" on Z_{p} for p a prime, and the van der Waerden numbers W(k) for 2 ≤ k ≤ 5, together with a computer search, have been used to determine the exact value of G(n) for 1 ≤ n ≤ 53, for all primes up to 71, and for a few more cases, the highest of which is G(695) = 5 which guarantees that W(6) ≥ 696.

Original language | English |
---|---|

Pages (from-to) | 211-221 |

Number of pages | 11 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 61 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1992 Nov |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics