On the Erdős-Hajnal Conjecture for Three Colors and Multiple Forbidden Triangles

by Lea Weber

Abstract:

Erdős and Szekeres’s quantitative version of Ramsey’s theorem asserts that any complete graph on $n$ vertices that is edge-colored with two colors has a monochromatic clique on at least $\frac{1}{2}\log n$ vertices. The famous Erdős-Hajnal conjecture asserts that forbidding fixed color patterns ensures larger monochromatic cliques. Specifically, it claims that for any fixed integer $k$ and any clique $K$ on $k$ vertices edge-colored with two colors, there is a positive constant $a$ such that in any complete $n$ -vertex graph edge-colored with two colors that does not contain a copy of $K$ , there is a monochromatic clique on at least $n^a$ vertices.

We consider edge-colorings with three colors. For a family $\tilde H$ of triangles, each colored with colors from ${r, b, y}$ , $\text{Forb}(n,\tilde H)$ denotes a family of edge-colorings of the complete $n$ -vertex graph using colors from ${r, b, y}$ and containing none of the colorings from $\tilde H$ . Let $h_2(n, \tilde H)$ be the maximum $q$ such that any coloring from $\text{Forb}(n, \tilde H)$ has a clique on at least $q$ vertices using at most two colors. We provide bounds on $h_2(n, \tilde H)$ for all families $\tilde H$ consisting of at most three triangles. For most of them, our bounds are asymptotically tight. This extends a result of Fox, Grinshpun, and Pach, who determined $h_2(n, \tilde H)$ for $\tilde H$ consisting of a rainbow triangle, and confirms the multicolor Erdős-Hajnal conjecture for these sets of patterns.