Abstract
A sequence of integers x1 < x2 < ··· < xk is called an ascending wave of length k if xi + 1 - xi ≤ xi + 2 - xi + 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 c1, c2 such that c1k3 ≤ f(k) ≤ c2k3 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 c3 and c4 such that c3(log n)2 log log n ≤ g(n) ≤ c4(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