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