Ascending waves

N. Alon, Joel Spencer

Research output: Contribution to journalArticle

8 Scopus citations

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 languageEnglish (US)
Pages (from-to)275-287
Number of pages13
JournalJournal of Combinatorial Theory, Series A
Volume52
Issue number2
DOIs
StatePublished - Nov 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Ascending waves'. Together they form a unique fingerprint.

  • Cite this