A multidimensional Ramsey Theorem
share
Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is still an exponential gap between the best known lower and upper bounds. For k-uniform hypergraphs, the bounds are of tower-type, where the height grows with k. Here, we give a multidimensional generalisation of Ramsey's Theorem to Cartesian products of graphs, proving that a doubly exponential upper bound suffices in every dimension. More precisely, we prove that for every positive integers r,n,d, in any r-colouring of the edges of the Cartesian product □^d K_N of d copies of K_N, there is a copy of □^d K_n such that the edges in each direction are monochromatic, provided that N≥ 2^2^C_drn^d. As an application of our approach we also obtain improvements on the multidimensional Erdős-Szekeres Theorem proved by Fishburn and Graham 30 years ago. Their bound was recently improved by Bucić, Sudakov, and Tran, who gave an upper bound that is triply exponential in four or more dimensions. We improve upon their results showing that a doubly expoenential upper bounds holds any number of dimensions.
READ FULL TEXT