کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656765 | 1632982 | 2015 | 51 صفحه PDF | دانلود رایگان |
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 Ω(n1/3log2n)Ω(n1/3log2n) 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≤rs≤r, we determine a constant cr,scr,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 Ω(ns(s−1)/r(r−1)(logn)cr,s)Ω(ns(s−1)/r(r−1)(logn)cr,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.
Journal: Journal of Combinatorial Theory, Series B - Volume 111, March 2015, Pages 75–125