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.