Sharp exponents for bipartite Erdős-Rado numbers

Dániel Dobák; Eion Mulrenin

paper

Sharp exponents for bipartite Erdős-Rado numbers

arXiv:2410.08982

Abstract

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 = E R (m)$ sufficiently large, any edge-coloring of $E (K_{n}) \to 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 $E R_{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 $lo g E R (m)$ are still separated by a factor of $lo g m$ .

9 pages, comments welcome. Version 2 includes some additional references and open problems