Remarks on a theorem of Erdős and Szemerédi

Abstract

Given a graph $G$ and a real $\epsilon >0$, an edge-coloring of $G$ is called $\epsilon$-balanced if each color appears on at least an $\epsilon$-fraction of the edges in $G$. A classical result of Erdős and Szemerédi asserts that if a $2$-edge-coloring of a complete graph $K_n$ is not $\epsilon$-balanced for some $0<\epsilon \le 1/2$, then there exists a large monochromatic clique. This theorem has been used extensively in Ramsey-type arguments, as it allows one to focus on reasonably balanced colorings. However, in its original formulation the dependence between $n$ and $\epsilon$ was left implicit, occasionally leading to inaccurate applications. In this short note, we revisit the Erdős--Szemerédi theorem and specify all parameter dependencies.

3 pages