



























We study Ramsey-type problems on sets avoiding sequences whose consecutive differences have a fixed relative order. For a given permutation $π\in S_k$, a $π$-wave is a sequence $x_1 < \cdots < x_{k+1}$ such that $x_{i+1} - x_i > x_{j+1} - x_j$ if and only if $π(i) > π(j)$. A subset of $[n] = \{1,\ldots,n\}$ is $π$-wave-free if it does not contain any $π$-wave. Our first main result shows that the size of the largest $π$-wave-free subset of $[n]$ is $O\left((\log n)^{k-1}\right)$. We then classify all permutations for which this bound is tight. In the cases where it is not tight, we prove stronger polylogarithmic upper bounds. We then apply these bounds to a closely related coloring problem studied by Landman and Robertson.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。