Tower heights for color-avoiding Ramsey numbers of monotone paths

Abstract

Ramsey numbers of monotone paths in ordered hypergraphs form a natural higher-uniformity extension of the classical Erdős--Szekeres theorems, and their tower height was determined by Moshkovitz and Shapira. A color-avoiding variant, initiated by Loh and further developed by Gowers and Long and by Mulrenin, Pohoata, and Zakharov, asks for monotone paths whose edges use only a bounded number of colors rather than a single color. For integers $q>p$, let $A_k(n;q,p)$ be the least integer $N$ such that every $q$-coloring of the ordered complete $k$-uniform hypergraph on $\{1,\dots ,N\}$ contains a monotone path of length $n$ whose edges use at most $p$ colors. We prove that, for every fixed $p$ and all sufficiently large $q$, the exact tower height of $A_k(n;q,p)$ is $\lceil (k-1)/p\rceil$. Thus the number of colors allowed on the path affects the Ramsey number at the level of tower height: allowing $p$ colors lowers the height from $k-1$ in the monochromatic problem to $\lceil (k-1)/p\rceil$. This answers questions of Mulrenin, Pohoata, and Zakharov. The upper bound follows from a simple block-compression argument. The main contribution is the matching lower bound, for which we develop a novel variant of the stepping-up method. A surprising feature of the proof is the appearance of the Morse--Hedlund theorem, a foundational result in symbolic dynamics and combinatorics on words. We establish and use a finite version of this theorem, which may be of independent interest.

22 pages. Major revisions throughout, including changes to the title and abstract. New upper bounds are added, and the exact tower height is determined