Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2602.03865 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |