Color avoidance for monotone paths

Color avoidance for monotone paths, Discrete Analysis 2025:23, 14 pp.

The famous Erdős–Szekeres theorem states that every sequence $a_1,\dots,a_{rs+1}$ of $rs+1$ real (and without loss of generality distinct) numbers has an increasing subsequence of length $r+1$ or a decreasing subsequence of length $s+1$. One way to prove it is to colour each pair of integers $mn$ with $m<n$ red if $a_m<a_n$ and blue if $a_m>a_n$. This gives us a red/blue colouring of the complete graph $K_{rs+1}$. Defining a path $m_1,\dots,m_k$ to be monotone if $m_1<\dots<m_k$, we see that it is sufficient to find a red monotone path of length $r+1$ or a blue monotone path of length $s+1$. To see that such a path must exist, we assign to each integer $m$ a pair of integers $(p(m),q(m))$, where $p$ is the length of the longest red monotone path that finishes at $m$ and $q$ is the length of the longest blue monotone path that finishes at $m$. One readily sees that if $m<m'$, then $p(m)<p(m')$ or $q(m)<q(m')$ (since the edge from $m$ to $m'$ can be appended to one or other of the longest monochromatic paths to $m$). It follows that all the pairs $(p(m),q(m))$ are distinct, and since there are $rs+1$ of them, it must be possible for $p(m)$ to take the value $r+1$ or for $q(m)$ to take the value $s+1$.

In 2015 Po-Shen Loh formulated a beautiful conjecture that is still open. Suppose that we 3-colour the edges of $K_n$. If we look for a monochromatic monotone path, then the argument given above generalizes straightforwardly, but what if instead we try to find a path that uses at most two colours, or equivalently that avoids one of the colours? With a bit of thought, one finds examples where the longest color-avoiding monotone path has length $n^{2/3}$, and the open question is whether this bound is best possible. If one imitates the proof technique described above, then one arrives at the following equivalent question. Define a sequence $((r_i,s_i,t_i))_{i=1}^n$ of triples of positive integers to be 2-increasing if whenever $i<j$, at least two of the inequalities $r_i<r_j, s_i<s_j$ and $t_i<t_j$ hold. Is it true that $n$ must be at most $m^{3/2}$ for every 2-increasing sequence of length $n$ with every $r_i, s_i$ and $t_i$ belonging to $\{1,2,\dots,m\}$? There is a trivial upper bound of $m^2$ (the pairs $(r_i,s_i)$ must be distinct). Loh observed that the triangle-removal lemma can be used to yield an upper bound of $o(m^2)$, and Gowers and Long improved that to $m^{2-c}$ for a very small absolute constant $c>0$, but the problem is still wide open.

This paper concerns generalizations of some of these ideas to hypergraphs. For this we first need to say what we mean by a “path” in a $k$-uniform hypergraph. The two commonest definitions are of loose paths, where consecutive edges intersect in exactly one vertex, and tight paths, where consecutive edges intersect in $k-1$ vertices. When $k=2$, these definitions coincide, but for $k>2$ they are very different. In this paper tight paths are considered. More precisely, the authors look at tight monotone paths, which are paths where one has a monotone sequence $v_1<v_2<\dots<v_{r+k-1}$ of vertices and the path consists of all edges of the form $\{v_i,v_{i+1},\dots,v_{i+k-1}\}$.

With that definition in place, one can ask questions analogous to the Erdős–Szekeres theorem and to the conjecture of Loh. To express these questions in a unified way, the authors define $A_k(n;r,s)$ to be the number $N$ of vertices you need if for every $r$-colouring of the edges of the complete $k$-uniform hypergraph with vertex set $\{1,2,\dots,N\}$ there is a tight monotone path that uses at most $s$ of the colours. For example, the Erdős–Szekeres theorem implies that $A_2(n;2,1)=(n-1)^2+1$, and Loh’s question turns out to be whether $A_2(n;3,2)$ is always at most $(n-1)^{3/2}+1$.

The question of generalizing the Erdős–Szekeres theorem was almost completely solved by Guy Moshkovitz and Asaf Shapira, who gave upper and lower bounds for $A_k(n;r,1)$, for every $k\geq 3$ and $r\geq 2$, that were both of the form a $(k-2)$-fold iterated exponential applied to a number of order of magnitude $n^{r-1}$. That is, they more or less determined how large $N$ needs to be if for every $r$-colouring of the complete $k$-uniform hypergraph with vertex set $\{1,2,\dots,N\}$ there is a monochromatic tight monotone path of length $n$.

This paper considers the colour-avoiding version of the problem. The main result is rather surprising: the authors show that the bound one obtains for the colour-avoiding version is not just better but much better, in that it beats the monochromatic version by an exponential. More precisely, the authors provide an upper bound for $A_k(n;r,s)$, showing that if $n\geq 3$ and $s>r/2$, then one needs not a $(k-2)$-fold iterated exponential but a $(k-3)$-fold iterated exponential, applied to a suitable power of $n$ that depends on $r$ and $s$ only. Note that when $k=3$ this implies that we do not need any exponentials, and indeed the first thing the authors do is prove that $A_3(n;3,2)$ is at most $n^9$.

The paper concludes with some appealing open problems. The most obvious is whether the upper bound provided in this paper can be matched by a lower bound, at least for the number of exponentials needed.