## Abstract

A sequence of integers x_{1} < x_{2} < ··· < x_{k} is called an ascending wave of length k if x_{i + 1} - x_{i} ≤ x_{i + 2} - x_{i + 1} for all 1 ≤ i ≤ k - 2. Let f(k) be the smallest positive integer such that any 2-coloring of {1, 2, ..., f(k)} contains a monochromatic ascending wave of length k. Settling a problem of Brown, Erdös, and Freedman we show that there are two positive constants c_{1}, c_{2} such that c_{1}k^{3} ≤ f(k) ≤ c_{2}k^{3} for all k ≥ 1. Let g(n) be the largest integer k such that any set A ⊆ {1, 2, ..., n} of cardinality |A| ≥ n 2 contains an ascending wave of length k. We show that there are two positive constants c_{3} and c_{4} such that c_{3}(log n)^{2} log log n ≤ g(n) ≤ c_{4}(log n)^{2} for all n ≥ 1.

Original language | English (US) |
---|---|

Pages (from-to) | 275-287 |

Number of pages | 13 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 52 |

Issue number | 2 |

DOIs | |

State | Published - Nov 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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