The Erdős-Hajnal conjecture for rainbow triangles
The Erdős-Hajnal conjecture for rainbow triangles
复制标题
DOI：
10.1016/j.jctb.2014.09.005
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
J. Fox;A. Grinshpun;J. Pach
中科院分区：
文献类型：
--
作者：
J. Fox;A. Grinshpun;J. Pach
证明了不含彩虹三角形的n阶完全图的边的每一个3-染色都包含一个至多使用两种颜色的阶数为Ω（n1/3log 2 <$n）的集合，并且这个界是紧的，直到一个常数因子.这验证了Hajnal的猜想，这是著名的Erdens-Hajnal猜想的一个推广。我们进一步建立了这个结果的推广。对于固定的正整数s和r，其中s≤ r，我们确定一个常数c r，s，使得以下成立。不含彩虹三角形的n个顶点上的完全图的边的每一个r-染色都包含一个阶数为Ω（ns（s− 1）/r（r− 1）（log <$n）c r，s）的至多使用s个颜色的集合，并且除了隐含的常数因子外，这个界是紧的。下界的证明利用了Gallai对完全图的彩虹三角形自由边着色的分类，Ramsey定理的一个新的加权扩展，以及边加权图中的一个差异不等式。上界的证明使用了Erdés关于Ramsey数的下界，通过考虑没有大单色团的完全图的2-边染色的字典序积。
We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Ω (n 1/3 log 2 n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjecture of Hajnal which is a case of the multicolor generalization of the well-known Erdős–Hajnal conjecture. We further establish a generalization of this result. For fixed positive integers s and r with s≤ r, we determine a constant c r, s such that the following holds. Every r-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Ω (n s (s− 1)/r (r− 1)(log n) c r, s) which uses at most s colors, and this bound is tight apart from the implied constant factor. The proof of the lower bound utilizes Gallai's classification of rainbow-triangle free edge-colorings of the complete graph, a new weighted extension of Ramsey's theorem, and a discrepancy inequality in edge-weighted graphs. The proof of the upper bound uses Erdős' lower bound on Ramsey numbers by considering lexicographic products of 2-edge-colorings of complete graphs without large monochromatic cliques.