A multidimensional Ramsey theorem

Journal article

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 ◻dKN of d copies of KN, there is a copy of ◻dKn such that the edges in each direction are monochromatic, provided that N≥22Cdrnd. 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.

Authors: Girao, A; Kronenberg, G; Scott, AD

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Alliance of Diamond Open Access Journals
• Journal: Discrete Analysis
• Volume: 24
• Publication date: 2024-12-31
• Acceptance date: 2024-08-20
• EISSN: 2397-3129
• Language: English
• Keywords: Ramsey Theory; Erd˝os-Szekeres