Sharp exponents for bipartite Erdős-Rado numbers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910700510642176 |
|---|---|
| author | Dobák, Dániel Mulrenin, Eion |
| author_facet | Dobák, Dániel Mulrenin, Eion |
| contents | The Erdős-Rado canonization theorem generalizes Ramsey's theorem to edge-colorings with an unbounded number of colors, in the sense that for $n = ER(m)$ sufficiently large, any edge-coloring of $E(K_n) \to \mathbb{N}$ will yield some copy of $K_m$ which is colored according to one of four canonical patterns. In this paper, we show that in the bipartite setting, the bipartite Erdős-Rado number $ER_B(m)$ satisfies \[ \log ER_B(m) = Θ(m \log m). \] Comparing this to the non-bipartite setting, the best known lower and upper bounds on $\log ER(m)$ are still separated by a factor of $\log m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08982 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sharp exponents for bipartite Erdős-Rado numbers Dobák, Dániel Mulrenin, Eion Combinatorics 05D10, 05C55 The Erdős-Rado canonization theorem generalizes Ramsey's theorem to edge-colorings with an unbounded number of colors, in the sense that for $n = ER(m)$ sufficiently large, any edge-coloring of $E(K_n) \to \mathbb{N}$ will yield some copy of $K_m$ which is colored according to one of four canonical patterns. In this paper, we show that in the bipartite setting, the bipartite Erdős-Rado number $ER_B(m)$ satisfies \[ \log ER_B(m) = Θ(m \log m). \] Comparing this to the non-bipartite setting, the best known lower and upper bounds on $\log ER(m)$ are still separated by a factor of $\log m$. |
| title | Sharp exponents for bipartite Erdős-Rado numbers |
| topic | Combinatorics 05D10, 05C55 |
| url | https://arxiv.org/abs/2410.08982 |