On the grid Ramsey problem and related questions
On the grid Ramsey problem and related questions
复制标题
关于网格拉姆齐问题及相关问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
Hales-Jewett定理是Ramsey理论的支柱之一，许多其他结果都来自于此。Shelah的一个著名定理说Hales-Jewett数是原始递归的。在他的证明中使用的一个关键工具，现在被称为立方体引理，已经因其本身而闻名。在最简单的形式中，这个引理说，如果我们将笛卡尔积Kn × Knin的边着色为r种颜色，那么，对于n足够大，存在一个矩形，其中两对相对的边接收相同的颜色。希拉的证明表明，n=r � r+1 2 � + 1就足够了。20多年前，Graham、Rothschild和Spencer提出了这样一个问题：这个界是否可以改进为r中的多项式。我们表明，这是不可能的，通过提供一个超多项式下界r。我们还讨论了一些相关的问题。
The Hales–Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales–Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product Kn × Knin r colors, then, for nsufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah’s proof shows that n=r � r+1 2 � + 1 suffices. More than 20 years ago, Graham, Rothschild, and Spencer asked whether this bound can be improved to a polynomial in r. We show that this is not possible by providing a superpolynomial lower bound in r. We also discuss a number of related problems.