Color-avoiding Ramsey for directed paths and vector sequences
Authors
Jacob Fox
Benny Sudakov
Yuval Wigderson
Abstract
We study two closely related Ramsey-type questions. The first is about vectors: how long can a sequence of vectors in $[n]^q$ be if, for all pairs in the sequence, the later vector is strictly larger than the earlier in at least $q-1$ coordinates? The second is graph-theoretic: given a $q$-edge-coloring of a tournament, how long of a directed path can we guarantee whose edges avoid one of the colors? These problems arise naturally in many areas, such as convex geometry and extremal hypergraph theory, and have been extensively studied over the past 50 years.
We prove that if $\varepsilon>0$ is fixed and $q$ is sufficiently large, then every $N$-vertex tournament contains a color-avoiding directed path of length $N^{1-\varepsilon}$. Consequently, the maximum length of a $(q-1)$-increasing sequence of vectors in $[n]^q$ has length at most $n^{1+\varepsilon}$. Our results answer a question of Gowers and Long, strengthen several of their results, and extend earlier works of Tiskin and Loh.
