A multidimensional Ramsey theorem

A multidimensional Ramsey theorem, Discrete Analysis 2024:21, 10 pp.

Ramsey’s theorem, the founding result of Ramsey theory, states that for every pair of positive integers \(r\) and \(k\) there exists \(n\) such that if the edges of the complete graph \(K_n\) on \(n\) vertices are coloured with \(r\) colours, then there must be \(k\) vertices all joined by edges of the same colour.

The main result of this paper is a multidimensional version of the theorem, in the following sense. Write \([n]\) for \(\{1,2,\dots,n\}\) and write \(K_n^d\) for the graph with vertex set \([n]^d\), where two vertices \(x\) and \(y\) are joined if there exists \(i\) such that \(x\) and \(y\) differ in the \(i\)th coordinate but in no other coordinate. To put it another way, if you fix all but one coordinate, then the result is a complete graph, and there are no further edges.

If \(n\) is sufficiently large and we colour the edges of \(K_n^d\) with \(r\) colours, can we hope to find a monochromatic \(K_k^d\)? Clearly not, even when \(k=r=2\), since we can colour all edges in direction 1 red and all other edges blue. However, what we can hope for is a \(K_k^d\) that for each direction, all the edges in that direction have the same colour. And indeed, it is easy to prove, with an iterated use of Ramsey’s theorem, that we can find such a \(K_k^d\).

Here is a sketch of the proof. Let \(n_1,\dots,n_d\) be a sufficiently rapidly growing sequence with \(n_1\) sufficiently large and colour \(K_{n_d}^d\) with \(r\) colours. Next, restrict this colouring to a colouring of \(K_{n_1}\times\dots\times K_{n_d}\). Now define an induced colouring of the edges of \(K_{n_d}\) by colouring each edge \(e\) by the way that \(K_{n_1}\times\dots\times K_{n_{d-1}}\times\{e\}\) is coloured. By Ramsey’s theorem, since \(n_d\) is sufficiently large, we can pass to a subset consisting of at least \(k\) of the vertices of \(K_{n_d}\) such that all these colourings are the same. This gives us an \(r\)-colouring of \(K_{n_1}\times\dots\times K_{n_{d-1}}\times K_k\) that does not depend on the last edge. By induction we can restrict it to a monochromatic copy of \(K_k^d\).

Unfortunately this argument iterates the bound for Ramsey’s theorem \(d\) times, so leads to a tower-type dependence on \(d\). In fact, even the case \(k=r=2\) is interesting from a quantitative point of view, partly because there is a large gap between the bound that comes from the argument just sketched and the best known lower bound, and partly because the question arises naturally in the context of trying to improve Shelah’s bound for the Hales-Jewett theorem. (The connection is explained in the second edition of Graham, Rothschild and Spencer’s book on Ramsey theory.)

The main result of this paper is a significant improvement to the above easy bound: by a surprisingly short but ingenious argument the authors obtain a dependence on \(d\) that is doubly exponential.

They then use a similar method to improve the best known bound for a multidimensional version of the Erdős-Szekeres theorem. The Erdős-Szekeres theorem itself states that every sequence of real numbers of length \(nm+1\) has an increasing sequence of length \(n\) or a decreasing sequence of length \(m\). In 1993 Fishburn and Graham proved a multidimensional version of this, where instead of a sequence one has a \(d\)-dimensional array of numbers. Writing such an array as a real-valued function \(f\) of \(d\) variables \(a_1,\dots,a_d\), where \(a_i\in\{1,2,\dots,n_i\}\), we call such an array increasing/decreasing in direction \(i\) if, however one fixes \(a_1,\dots,a_{i-1},a_{i+1},\dots,a_d\), \(f\) is increasing/decreasing as a function of \(a_i\). The theorem of Fishburn and Graham states that if \(n\) is large enough, then for every \(d\)-dimensional array with \(n_1=n_2=\dots=n_d=n\), one can find subsets \(A_i\subset\{1,2,\dots,n_i\}\) such that for every \(i\) the restriction of the array to \(A_1\times\dots\times A_d\) is increasing or decreasing.

Fishburn and Graham’s proof gave an Ackermann-type dependence of \(n\) on \(d\). This bound was greatly improved in 2022 by Bucić, Sudakov and Tran to a triply exponential bound, who conjectured that a doubly exponential bound ought to be sufficient. Their conjecture is confirmed in this paper.