An Explicit Construction for a Ramsey Problem
An Explicit Construction for a Ramsey Problem
复制标题
拉姆齐问题的显式构造
DOI：
10.1007/s00493-004-0019-6
复制
发表时间：
2004
期刊：
影响因子：
1.1
通讯作者：
D. Mubayi
中科院分区：
文献类型：
--
作者：
D. Mubayi
构造Kn的边的显式着色，使得K4的每个副本在其边上至少有四种颜色。当n → ∞时，使用的颜色数为n1/2+o（1）。这改进了埃尔德什和吉亚法斯通过概率方法获得的先前O（n2/3）的界。指数1/2是最优的，因为已知在这样的着色中至少需要Ω（n1/2）种颜色。然而，由于对颜色类别之间的交互施加了限制，因此它更加复杂。
An explicit coloring of the edges of Kn is constructed such that every copy of K4 has at least four colors on its edges. As n → ∞, the number of colors used is n1/2+o(1). This improves upon the previous bound of O(n2/3) due to Erdős and Gyárfás obtained by probabilistic methods. The exponent 1/2 is optimal, since it is known that at least Ω(n1/2) colors are required in such a coloring.The coloring is related to constructions giving lower bounds for the multicolor Ramsey number rk(C4). It is more complicated however, because of restrictions imposed on interactions between color classes.