The Erdos-Hajnal conjecture for rainbow triangles

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 ohm(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 Erdos-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 ohm(n(s(s-1)/r(r-1))(log n)(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 Erdos' lower bound on Ramsey numbers by considering lexicographic products of 2-edge-colorings of complete graphs without large monochromatic cliques. (C) 2014 Elsevier Inc. All rights reserved.


Published in:
Journal Of Combinatorial Theory Series B, 111, 75-125
Year:
2015
Publisher:
San Diego, Academic Press Inc Elsevier Science
ISSN:
0095-8956
Keywords:
Laboratories:




 Record created 2015-04-13, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)