A multidimensional Ramsey Theorem

Authors António Girão, Gal Kronenberg, Alex Scott

Publication date 17 October 2022

Abstract: 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

s q u a r e^{d} K_{N}

of

d

copies of

K_{N}

, there is a copy of

s q u a r e^{d} K_{n}

such that the edges in each direction are monochromatic, provided that

N g e q 2^{2^{C_{d} r n^{d}}}

. As an application of our approach we also obtain improvements on the multidimensional ErdH{o}s-Szekeres Theorem proved by Fishburn and Graham

30

years ago. Their bound was recently improved by Buci'c, 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.

This page was built for publication: A multidimensional Ramsey Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414211)