论文标题
多维拉姆西定理
A multidimensional Ramsey Theorem
论文作者
论文摘要
拉姆西理论是组合学的中心和积极分支。尽管自1930年代拉姆齐（Ramsey）的作品以来，对图形的拉姆齐（Ramsey）数字进行了广泛的研究，但最著名的下层和上限之间仍然存在指数差距。对于$ k $均匀的超图，界限是塔式的，那里的高度在$ k $中增长。在这里，我们将拉姆齐定理的多维概括对笛卡尔产物进行了图形产品，证明了每个维度在每个维度上都足以达到指数的上限。更准确地说，我们证明，对于每一个积极的整数$ r，n，d $，在任何$ r $ r $ - 颜色的颜色的笛卡尔产品边缘$ \ square^{d} k_n $ of $ d $ of $ k_n $ of $ k_n $的副本，$ \ square^d} k_n $的副本是$ \ square^{d} k_n $ nepe n $ n ge ge in $ n ge ge n n Deeprance in monoch 2^{2^{c_drn^{d}}} $。作为我们方法的应用，我们还获得了Fishburn和Graham $ 30 $几年前证明的多维Erdős-Szekeres定理的改进。 Bucić，Sudakov和Tran最近改善了他们的界限，他们的上限在四个或以上的维度上呈三重指数。我们改进了他们的结果，表明双重指数上限具有任何数量的维度。
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 $\square^{d} K_N$ of $d$ copies of $K_N$, there is a copy of $\square^{d} K_n$ such that the edges in each direction are monochromatic, provided that $N\geq 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.
