Id: arxiv/2602.03865 Url: https://arxiv.org/abs/2602.03865 Tags: math.CO Score: 0 Title: Remarks on a theorem of Erdős and Szemerédi Domain: math.CO Source: arxiv Authors: Dingyuan Liu Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-01-30 Page: https://delphi.science/r/arxiv/2602.03865 Given a graph $G$ and a real $\varepsilon>0$, an edge-coloring of $G$ is called $\varepsilon$-balanced if each color appears on at least an $\varepsilon$-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 $\varepsilon$-balanced for some $0<\varepsilon\leq1/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…