Contents Online

# Journal of Combinatorics

## Volume 11 (2020)

### Number 1

### Monochromatic balanced components, matchings, and paths in multicolored complete bipartite graphs

Pages: 35 – 45

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n1.a2

#### Authors

#### Abstract

It is well-known that in every r-coloring of the edges of the complete bipartite graph $K_{n,n}$ there is a monochromatic connected component with at least $\frac{2n}{r}$ vertices. It would be interesting to know whether we can additionally require that this large component be balanced; that is, is it true that in every $r$-coloring of $K_{n,n}$ there is a monochromatic component that meets both sides in at least $n/r$ vertices?

Over forty years ago, Gyárfás and Lehel and independently Faudree and Schelp proved that any $2$-colored $K_{n,n}$ contains a monochromatic $P_n$. Very recently, Bucić, Letzter and Sudakov proved that every $3$-colored $K_{n,n}$ contains a monochromatic connected matching (a matching whose edges are in the same connected component) of size $\lceil n / 3 \rceil$. So the answer is strongly “yes” for $1 \leq r \leq 3$.

We provide a short proof of (a non-symmetric version of) the original question for $1 \leq r \leq 3$; that is, every $r$-coloring of $K_{m,n}$ has a monochromatic component that meets each side in a $1/r$ proportion of its part size. Then, somewhat surprisingly, we show that the answer to the question is “no” for all $r \geq 4$. For instance, there are $4$-colorings of $K_{n,n}$ where the largest balanced monochromatic component has $n/5$ vertices in both partite classes (instead of $n/4$). Our constructions are based on lower bounds for the $r$-color bipartite Ramsey number of $P_4$, denoted $f(r)$, which is the smallest integer $\ell$ such that in every $r$-coloring of the edges of $K_{\ell ,\ell}$ there is a monochromatic path on four vertices. Furthermore, combined with earlier results, we determine $f(r)$ for every value of $r$.

#### Keywords

Ramsey, bipartite graph

#### 2010 Mathematics Subject Classification

05C38, 05C55

The research of L. DeBasio was supported in part by Simons Foundation Collaboration Grant #283194.

The research of A. Gyárfás was supported in part by NKFIH Grant No. K116769.

The research of M. Ruszinkó was supported in part by NKFIH Grant No. K116769.

Received 21 April 2018

Published 27 September 2019