Remarks on a theorem of Erdős and Szemerédi
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.03865
curl -X POST /api/v1/records/arxiv/2602.03865/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.03865/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'