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

Louis DeBiasio (Department of Mathematics, Miami University, Oxford, Ohio, U.S.A.)

András Gyárfás (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Robert A. Krueger (Department of Mathematics, Miami University, Oxford, Ohio, U.S.A.)

Miklós Ruszinkó (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Gábor N. Sárközy (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary; and Computer Science Department, Worcester Polytechnic Institute, Worcester, Massachusetts, U.S.A.)

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

Received 21 April 2018

Published 27 September 2019