Remarks on a theorem of Erdős and Szemerédi
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915796816494592 |
|---|---|
| author | Liu, Dingyuan |
| author_facet | Liu, Dingyuan |
| contents | 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 $\varepsilon$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_03865 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Remarks on a theorem of Erdős and Szemerédi Liu, Dingyuan Combinatorics 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 $\varepsilon$ 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. |
| title | Remarks on a theorem of Erdős and Szemerédi |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.03865 |