Bounds for Bipartite Rainbow Ramsey Numbers

Abstract

Given bipartite graphs G and H, the bipartite rainbow Ramsey number BRR(G; H) is the minimum integer N such that any edge-coloring of $K_{N,N}$ with any number of colors contains either a monochromatic copy of G or a rainbow copy of H. It is known that BRR(G; H) exists if and only if G is a star or H is a forest consisting of stars. For fixed $t\ge 3$, $s\ge (t-1)!+1$ and large n, we shall show that $BRR(K_{t,s};K_{1,n})=\varTheta (n^t)$ and $BRR(K_{1,n};K_{t,t})=\varTheta (n)$. We also improve the known bounds for $BRR(C_{2m};K_{1,n})$, $BRR(K_{1,n};C_{2m})$, $BRR(B_{s,t};K_{1,n})$ and $BRR(K_{1,n};B_{s,t})$, where $B_{s,t}$ is a broom consisting of $s+t$ edges obtained by identifying the center of star $K_{1,s}$ with an end-vertex of a path $P_{1+t}$. Particularly, we have $BRR(C_{2m};K_{1,n})\ge (1-o(1))n^{m/(m-1)}$ for $m=2,3,5$ and large n.

1 Introduction

Let G be a graph. A monochromatic coloring of G is an edge-coloring of G by a single color, and a rainbow coloring of G is an edge-coloring of G whose edges have pairwise distinct colors. The Ramsey number $R_k(G)$ is the smallest integer N such that in any k-coloring of the edges of $K_N$, there is a monochromatic copy of G.

For graphs G and H, the rainbow Ramsey number RR(G; H) is defined to be the minimum integer N such that any edge-coloring of $K_N$ using any number of colors contains either a monochromatic copy of G or a rainbow copy of H, see Eroh [5]. Jamison et al. [9] proved that RR(G; H) exists if and only if G is a star or H is a forest consisting of stars. Results for bounding RR(G; H) with various types of parameters can be found in literature, see [2, 8, 10, 13].

Given two bipartite graphs G and H, the bipartite rainbow Ramsey number BRR(G; H) is the minimum integer N such that any edge-coloring of $K_{N,N}$ with any number of colors contains either a monochromatic copy of G or a rainbow copy of H. For an extended survey regarding bounds for rainbow Ramsey numbers and bipartite rainbow Ramsey numbers, see [7].

The following two bounds were obtained by Eroh and Oellermann [6].

Lemma 1

[6] Let G and H be connected bipartite graphs. Then BRR(G; H) exists if and only if G or H is a star.

Lemma 2

[6] Let $G_n$ and $B_m$ be bipartite graphs such that $G_n$ is connected and has n vertices in the larger part, and $B_m$ has m edges. If $BRR(G_n;B_m)$ exists, then $BRR(G_n;B_m)\ge (n-1)(m-1)+1$.

Moreover, they proved that $3n-2\le BRR(K_{1,n};C_{4})\le 6n-8$, where $K_{1,n}$ is a star with n edges and $C_{4}$ is a 4-cycle. Later, Balister et al. [3] restated the bipartite rainbow Ramsey number in terms of matrices. By a construction, they found $BRR(K_{1,n};C_4)=3n-2$, verifying that the lower bound is the exact value. We shall consider $BRR(K_{t,s};K_{1,n})$ and $BRR(K_{1,n};K_{t,t})$.

We need another definition in the proofs. Given graphs G and H, Erdős et al. [4] defined the anti-Ramsey number AR(G; H) to be the maximum number k of colors such that there exists an edge-coloring of G with exactly k colors in which every copy of H in G is not rainbow colored. Let $P_{1+t}$ be a path with t edges, and $B_{s,t}$ a broom consisting of $s+t$ edges obtained by identifying the center of a star $K_{1,s}$ with an end-vertex of $P_{1+t}$. Jiang and West [11] derived bounds for $AR(K_n;B_{s,t})$.

In Sect. 2, we show $BRR(K_{t,s};K_{1,n})=\varTheta (n^t)$ for fixed $t\ge 3$, $s\ge (t-1)!+1$ and large n. And in Sect. 3, we give $t^2(n-1)+1\le BRR(K_{1,n};K_{t,t})\le t^3(n-1)+t-1$ for $n>t\ge 3$. In last two sections, we consider $BRR(C_{2m};K_{1,n})$, $BRR(K_{1,n};C_{2m})$, $BRR(B_{s,t};K_{1,n})$ and $BRR(K_{1,n};B_{s,t})$. Particularly, we have $BRR(C_{2m};K_{1,n})\ge (1-o(1))n^{m/(m-1)}$ for $m=2,3,5$ and large n.

2 Bounding $BRR(K_{t,s};K_{1,n})$

To prove the existence of $BRR(K_{t,t};K_{1,n})$, Eroh and Oellermann [6] showed that for any positive integers t and n,

$$\begin{aligned} (t-1)(n-1)+1\le BRR(K_{t,t};K_{1,n})\le (t-1)(n-1)^{(t-1)(n-1)+1}+1. \end{aligned}$$

(1)

We shall improve Eq. (1) as follows.

Theorem 1

For fixed integers t and s with $t\ge 3$, $s\ge (t-1)!+1$,

$$\begin{aligned} BRR(K_{t,s};K_{1,n}) =\varTheta (n^t). \end{aligned}$$

We need a relationship between Ramsey numbers and bipartite rainbow Ramsey numbers.

Lemma 3

Let G be a complete bipartite graph with order $|G|\ge 3$. Then for any integer $n\ge 4$,

$$\begin{aligned} R_{n-2}(G)\le BRR(G;K_{1,n}). \end{aligned}$$

Proof

Let $N=R_{n-2}(G)-1$ and $K_N$ be a complete graph with vertex set $\{a_1,\ldots ,a_N\}$. Then there is an edge-coloring of $K_N$ with $n-2$ colors containing no monochromatic copy of G. Consider $K_{N,N}$ on bipartition $U=\{u_1,\ldots ,u_N\}$ and $V=\{v_1,\ldots ,v_N\}$. For $i\ne j$, color the edge $u_iv_j$ in $K_{N,N}$ by the color of $a_ia_j$ in $K_N$. Color the edges $\{u_iv_i\mid 1\le i\le N\}$ by a new color, which form a monochromatic matching of N edges. Since the total number of colors is $n-1$, there is no rainbow copy of $K_{1,n}$ in $K_{N,N}$.

Suppose that $G=K_{t,s}$ and there is a monochromatic G in $K_{N,N}$. Let $\{u_{p_1},\ldots ,u_{p_t},v_{q_1},\ldots ,v_{q_s}\}$ be the vertex set of G in $K_{N,N}$. Since $|G|\ge 3$, then $G\ne K_{1,1}$. And G is a monochromatic copy of $K_{t,s}$, we see that $p_i\ne q_j$ for any $1\le i\le t$ and $1\le j\le s$. Then the edge set $\{a_{p_i}a_{q_j}\mid 1\le i\le t, 1\le j\le s\}$ forms a monochromatic copy of $K_{t,s}$ in $K_N$, yielding a contradiction. $\square$

The following was obtained by Alon et al. [1].

Lemma 4

Let $t\ge 2$ and $s\ge (t-1)!+1$ be fixed integers. Then

$$\begin{aligned} R_n(K_{t,s})= \varTheta (n^t). \end{aligned}$$

Given positive integers t, s, n and b, define $a_{t,s}(n;b)$ to be the smallest integer a such that in any $b\times a$ matrix A either there is a $t\times s$ sub-matrix B whose elements are all the same or there are at least n distinct elements in some row or column. Observe that for $b\le (n-1)(t-1)$, $a_{t,s}(n;b)$ is undefined: consider any number of columns, each filled with at most $n-1$ symbols repeated at most $t-1$ times(using the same $n-1$ symbols in distinct columns).

For positive integers b, t and n with $b>(n-1)(t-1)$, given a b-tuple $z=(z_1,\ldots ,z_{b})$, let q(z, t) be the number of subsets $T\subseteq \{1,\dots ,b\}$ with $|T|=t$ such that all the elements $z_i$, $i\in T$, are the same. Set q(n, b, t) to be the minimum value of q(z, t) over all b-tuples z for which the distinct elements of z are less than n in z. If $b=p(n-1)+r$, $0\le r<n-1$, then an optimal b-tuple z contains $n-r-1$ entries repeated p times and r entries repeated $p+1$ times. So we get

$$\begin{aligned} q(n,b,t)=(n-r-1)\left( {\begin{array}{c}p\\ t\end{array}}\right) +r\left( {\begin{array}{c}p+1\\ t\end{array}}\right) . \end{aligned}$$

Lemma 5

For positive integers t, s, n and b with $b>(n-1)(t-1)$,

$$\begin{aligned} a_{t,s}(n;b)\le 1+\left( {\begin{array}{c}b\\ t\end{array}}\right) (n-1)(s-1)\frac{1}{q(n,b,t)}. \end{aligned}$$

Proof

Assume that A is a $b\times a$ extremal matrix with $a=a_{t,s}(n;b)-1$ such that A has no $t\times s$ sub-matrix whose elements are all the same and the number of the distinct elements in each row or column are less than n.

Every column of A has at least q(n, b, t) t-tuples of the same elements, so A has at least q(n, b, t)a t-tuples of the same elements in its columns. Therefore at least $q(n,b,t)a/\left( {\begin{array}{c}b\\ t\end{array}}\right)$ of these t-tuples are placed along the same set of t rows. Since A has no $t\times s$ submatrix whose elements are all the same and the distinct elements in each row are less than n, we obtain

$$\begin{aligned} q(n,b,t)a/\left( {\begin{array}{c}b\\ t\end{array}}\right) \le (n-1)(s-1), \end{aligned}$$

implying the required inequality. $\square$

Now we consider the bounds for $BRR(K_{t,s};K_{1,n})$.

Proof of Theorem 1

The lower bound follows from Lemmas 3 and 4.

For the upper bound, assume that A is a $b\times a$ matrix with $a=a_{t,s}(n;b)$. Set $b=(s-1)(n-1)^t$. Then

$$\begin{aligned} q(n,b,t)=(n-1)\left( {\begin{array}{c}(s-1)(n-1)^{t-1}\\ t\end{array}}\right) . \end{aligned}$$

By Lemma 5, we obtain that for large n, $a_{t,s}(n;b)$ is at most

$$\begin{aligned}&1+\left( {\begin{array}{c}b\\ t\end{array}}\right) (n-1)(s-1)\frac{1}{q(n,b,t)} \le 1+\frac{(n-1)(s-1)\left( {\begin{array}{c}(s-1)(n-1)^t\\ t\end{array}}\right) }{(n-1)\left( {\begin{array}{c}(s-1)(n-1)^{t-1}\\ t\end{array}}\right) }\\&\quad \le 1+(s-1)\frac{ \Big ((s-1)(n-1)^t\times \big ((s-1)(n-1)^t-1\big )\times \ldots \times \big ((s-1)(n-1)^t-t+1\big ) \Big )/t! }{\Big ((s-1)(n-1)^{t-1}\times \big ((s-1)(n-1)^{t-1}-1\big )\times \cdots \times \big ((s-1)(n-1)^{t-1}-t+1\big )\Big )/t! }\\&\quad \le 1+(s-1)\left( \frac{(s-1)(n-1)^t}{(s-1)(n-1)^{t-1}-t+1}\right) ^t \le 1+(s-1)\left( \frac{(n-1)^t}{(n-1)^{t-1}-\frac{t-1}{s-1}}\right) ^t. \end{aligned}$$

Let $\delta =\frac{t-1}{s-1}$ and $\epsilon =\frac{\delta (n-1)}{(n-1)^{t-1}-\delta }$. Then we have $\delta =\frac{\epsilon (n-1)^{t-1}}{n-1+\epsilon }$ and we obtain that

$$\begin{aligned} a_{t,s}(n;b)&\le 1+(s-1)\left( \frac{(n-1)^t}{(n-1)^{t-1}-\delta }\right) ^t\\&=1+(s-1)\left( \frac{(n-1)^t}{(n-1)^{t-1}-\frac{\epsilon (n-1)^{t-1}}{n-1+\epsilon }}\right) ^t\\&=1+(s-1)\left( \frac{n-1}{1-\frac{\epsilon }{n-1+\epsilon }}\right) ^t=1+(s-1)(n-1+\epsilon )^t, \end{aligned}$$

which implies that $a_{t,s}(n;b)< (s-1)n^t$ for large n.

Then we obtain that for large n, in any edge-coloring of $K_{(s-1)(n-1)^t,(s-1)n^t}$ with any number of colors, either there is a monochromatic copy of $K_{t,s}$, or there is a rainbow copy of $K_{1,n}$. Since $K_{(s-1)(n-1)^t,(s-1)n^t}$ is a subgraph of $K_{(s-1)n^t,(s-1)n^t}$, we have in any edge-coloring of $K_{(s-1)n^t,(s-1)n^t}$ with any number of colors, either there is a monochromatic copy of $K_{t,s}$, or there is a rainbow copy of $K_{1,n}$, which implies $BRR(K_{t,s};K_{1,n})\le (s-1)n^t$. $\square$

3 Bounding $BRR(K_{1,n};K_{t,t})$

To prove the existence of $BRR(K_{1,n};K_{t,t})$, Eroh and Oellermann [6] showed that for integers $n\ge 2$ and $t\ge 1$,

$$\begin{aligned} (n-1)(t^{2}-1)+1\le BRR(K_{1,n};K_{t,t})\le \lceil \frac{1}{2}t^2(t-1)(tn+n-t-3)+2\rceil . \end{aligned}$$

(2)

For $t=2$, Balister et al. [3] proved the lower bound is the exact value. We shall improve the upper bound in Eq. (2) as follows with similar proof from Balister et al. [3].

Theorem 2

For any integer $n\ge 4$,

$$\begin{aligned} BRR(K_{1,n};K_{3,3})\le 17n-15. \end{aligned}$$

(3)

And for integers n and t with $n>t\ge 3$,

$$\begin{aligned} BRR(K_{1,n};K_{t,t})\le t^3(n-1)+t-1. \end{aligned}$$

(4)

For the proofs, we need some definitions. Given positive integers n, t and b, define $a_n(t,t;b)$ be the smallest integer a such that in any $b\times a$ matrix either some entry is repeated at least n times in some row or column or there is a $t\times t$ sub-matrix with distinct elements. Observe that for $b\le (n-1)(t-1)$, $a_n(t,t;b)$ is undefined: consider any number of columns, each filled with $t-1$ symbols repeated $n-1$ times(using distinct symbols in distinct columns). For positive integers b, n and t with $b>(n-1)(t-1)$, given $z=(z_1,\ldots ,z_{b})$, let p(z, t) be the number of t-tuple subsets $T\subseteq \{1,\cdots ,b\}$ such that the t elements $z_i$, $i\in T$, are all distinct. Let p(n, b, t) be the minimum value of p(z, t) over all b-tuples z for which every element of z is repeated less than n times in z. It is well known that if $b=q(n-1)+r$, $0\le r<n-1$, then z contains q entries repeated $n-1$ times and one entry repeated r times. Hence

$$\begin{aligned} p(n,b,t)=\left( {\begin{array}{c}q\\ t\end{array}}\right) (n-1)^t+\left( {\begin{array}{c}q\\ t-1\end{array}}\right) (n-1)^{t-1}r. \end{aligned}$$

The following was obtained by Balister et al. [3].

Lemma 6

For positive integers n, t and b with $b>(n-1)(t-1)$,

$$\begin{aligned} a_n(t,t;b)\le 1+\left( {\begin{array}{c}b\\ t\end{array}}\right) (t^2-t+1)(t-1)(n-1)\frac{1}{p(n,b,t)}. \end{aligned}$$

Proof of the upper bound (3)

Assume that A is a $b\times a$ matrix with $a=a_n(3,3;b)$. Then A has either some entry repeated at least n times in some row or column, or a $3\times 3$ sub-matrix with distinct elements. Set $b=17(n-1)+2$. Then

$$\begin{aligned} p(n,b,3)=\left( {\begin{array}{c}17\\ 3\end{array}}\right) (n-1)^3+2\left( {\begin{array}{c}17\\ 2\end{array}}\right) (n-1)^2. \end{aligned}$$

By Lemma 6, we obtain

$$\begin{aligned} a_n(3,3;b)\le & {} 1+14\left( {\begin{array}{c}17(n-1)+2\\ 3\end{array}}\right) (n-1)\frac{1}{p(n,b,3)}\\\le & {} 1+\frac{119(n-1)+14}{120(n-1)+48}(17(n-1)+1)\le 17n-15. \end{aligned}$$

Then we have $a_n(3,3;17n-15)\le 17n-15$. Hence $BRR(K_{1,n};K_{3,3})\le 17n-15$.

$\square$

Proof of the upper bound (4)

Assume that A is a $b\times a$ matrix with $a=a_n(t,t;b)$. Set $b=t^3(n-1)+t-1$. Since $n>t$, then we have

$$\begin{aligned} p(n,b,t)=\left( {\begin{array}{c}t^3\\ t\end{array}}\right) (n-1)^t+(t-1)\left( {\begin{array}{c}t^3\\ t-1\end{array}}\right) (n-1)^{t-1}. \end{aligned}$$

By Lemma 6, we obtain that

$$\begin{aligned} a_n(t,t;b)\le & {} 1+ \left( {\begin{array}{c}t^3(n-1)+t-1\\ t\end{array}}\right) (t^2-t+1)(t-1)(n-1)\frac{1}{p(n,b,t)}\\\le & {} 1+\frac{\left( t^3(n-1)+t-1\right) ^{t-2}(t^2-t+1)(t-1)}{(n-1)^{t-3} (t^3-t+2)^{t-2}((t^3-t+1)(n-1)+t(t-1))}\left( t^3(n-1)+t-2\right) \\\le & {} 1+(\frac{t^3+t-1}{t^3-t+2})^{t-2}\frac{(t^2-t+1)(t-1)(n-1)}{(t^3-t+1)(n-1)+t(t-1)}\left( t^3(n-1)+t-2\right) . \end{aligned}$$

Set functions $g(t)=\frac{t^3-t+1}{(t-1)(t^2-t+1)}$, $h(t)=\left( \frac{t^3+t-1}{t^3-t+2}\right) ^{t-2}$, and we have $a_n(t,t;b)\le 1+\frac{h(t)}{g(t)}\left( t^3(n-1)+t-2\right)$.

For $t\ge 3$,

$$\begin{aligned} h(t)= & {} \left( 1+\frac{2t-3}{t^3-t+2}\right) ^{t-2}\le e^{\frac{(t-2)(2t-3)}{t^3-t+2}}\\\le & {} 1+\frac{(t-2)(2t-3)}{t^3-t+2}+\frac{e}{2}\frac{(t-2)^2(2t-3)^2}{(t^3-t+2)^2}\\\le & {} 1+\frac{(t-2)(2t-3)}{t^3-t+2}+2\frac{(t-2)^2(2t-3)^2}{(t^3-t+2)^2}. \end{aligned}$$

Then we have

$$\begin{aligned} g(t)-h(t)\ge & {} \frac{t^3-t+1}{(t-1)(t^2-t+1)}-1-\frac{(t-2)(2t-3)}{t^3-t+2}-2\frac{(t-2)^2(2t-3)^2}{(t^3-t+2)^2}\\\ge & {} \frac{8t^4-24t^3+35t^2-27t+10}{(t^3-t+2)(t^3-2t^2+2t-1)}-2\frac{(t-2)^2(2t-3)^2}{(t^3-t+2)^2}\\\ge & {} \frac{8t^4-24t^3+35t^2-27t+10}{(t^3-t+2)^2}-2\frac{(t-2)^2(2t-3)^2}{(t^3-t+2)^2}\\\ge & {} \frac{32t^3-111t^2+141t-62}{(t^3-t+2)^2}. \end{aligned}$$

So $g(t)\ge h(t)$ for $t\ge 3$. And hence $a_n(t,t;b)\le t^3(n-1)+t-1$. $\square$

4 $BRR(C_{2m};K_{1,n})$ and $BRR(K_{1,n};C_{2m})$

Here we shall show the lower bound for $BRR(C_{2m};K_{1,n})$ as follows.

Theorem 3

For $m=2,3,5$, if $n\rightarrow \infty$, then

$$\begin{aligned} BRR(C_{2m};K_{1,n})\ge (1-o(1))n^{m/(m-1)}. \end{aligned}$$

Let $m\ge 2$ be an integer and $q\ge m$ be a prime power. Let F(q) be the Galois field of q elements, and both X and Y be copies of the Cartesian product $F^m(q)$. Denote by N the number $q^m=|X|=|Y|$. We shall use vectors in $F^{m-1}(q)$ as colors to color the complete bipartite graph $K_{N,N}$ on partite sets X and Y such that there is no monochromatic copy of $C_{2m}$ for $m=2,3,5$. For vertices $A\in X$ and $B\in Y$ with

$$\begin{aligned} A=\left( \begin{array}{c} a_1\\ a_2\\ \vdots \\ a_m\\ \end{array} \right) \hbox { and } B=\left( \begin{array}{c} b_1\\ b_2\\ \vdots \\ b_m\\ \end{array} \right) , \end{aligned}$$

color the edge AB with color $S\in F^{m-1}(q)$ when

$$\begin{aligned} S=\left( \begin{array}{c} a_1+b_1\\ a_2+b_2\\ \vdots \\ a_{m-1}+b_{m-1}\\ \end{array} \right) +b_m \left( \begin{array}{c} a_2\\ a_3\\ \vdots \\ a_m\\ \end{array} \right) . \end{aligned}$$

Let us denote by $H_S(m,q)$ the subgraph induced by all edges in the color S.

The following was obtained by Li and Lih [12].

Lemma 7

Let $S\in F^{m-1}(q)$ and $q\ge m \ge 2$. Then $H_S(m,q)$ contains no monochromatic $C_{2m}$ for $m=2,3,5$.

Proof of Theorem 3

Let $p_1$ and $p_2$ be consecutive primes such that $p_1^{m-1}\le n-1<p_2^{m-1}$. From the Prime Number Theorem, we know $p_1\sim p_2$ and hence $p_1^{m-1}\sim n$ as $n\rightarrow \infty$. By the definition of $H_S(m,p_1)$, we use $p_1^{m-1}\le n-1$ colors to color $K_{N,N}$, $N=p_1^m$, such that it contains neither a rainbow copy of $K_{1,n}$ nor a monochromatic copy of $C_{2m}$ by Lemma 7. Thus, $BRR(C_{2m};K_{1,n})$ is at least $N=p_1^m\ge (1-o(1))n^{m/(m-1)}$. $\square$

For fixed m, $BRR(C_{2m};K_{1,n})$ is nonlinear on n. However, $BRR(K_{1,n};C_{2m})$ is linear on n. Especially, for $m=2$, $BRR(K_{1,n};C_4)=BRR(K_{1,n};K_{2,2})=3n-2$ which is determined completely, see [3]. By borrowing the method of Eroh and Oellermann [6], we obtain the bounds for $BRR(K_{1,n};C_{2m})$.

Theorem 4

For any integers $n,m \ge 2$,

$$\begin{aligned} (2m-1)(n-1)+1\le BRR(K_{1,n};C_{2m})\le 4m(n-2)+m(m-1)(n-1)+2. \end{aligned}$$

Furthermore, for m odd, the lower bound can be improved to $2m(n-1)+1$.

Proof

For the lower bound, by Lemma 2, $BRR(K_{1,n};C_{2m})\ge (2m-1)(n-1)+1$.

For m odd, let $M=2m(n-1)$. Consider a $K_{2m,2m}$ on bipartition $U=\{u_0,u_1,\ldots ,u_{2m-1}\}$ and $V=\{v_0,v_1,\ldots ,v_{2m-1}\}$. We define the color C(e) of each edge e in $K_{2m,2m}$ as follows. For any $i,j\in \{0,1,\ldots ,2m-1\}$, let $C(u_iv_j)\equiv i+j \;(\text{ mod }\,2m)$. We claim that any pair of adjacent edges are in different colors. If not, suppose $C(u_iv_{j_1})=C(u_iv_{j_2})$ with $j_{1}\ne j_{2}$, then $j_1\equiv j_2 \;(\text{ mod }\,2m)$. Since $j_1,j_2\in \{0,1,\ldots ,2m-1\}$, we have $j_1=j_2$, for a contradiction. Now replace each $u_i$ and each $v_j$ with $n-1$ new vertices to produce a copy of $K_{M,M}$. Thus, there is no monochromatic copy of $K_{1,n}$.

Suppose that there is a rainbow copy of $C_{2m}$ with the edge set $\{u_{i_1}v_{j_1},v_{j_1}u_{i_2},u_{i_2}v_{j_2},\ldots ,u_{i_m}v_{j_m},v_{j_m}u_{i_1}\}$. Divide the set into $E=\{u_{i_1}v_{j_1},u_{i_2}v_{j_2},\ldots ,u_{i_m}v_{j_m}\}$ and $E'=\{v_{j_1}u_{i_2},v_{j_2}u_{i_3},\ldots ,v_{j_{m-1}}u_{i_m},v_{j_m}u_{i_1}\}$.

Then we have

$$\begin{aligned} \displaystyle {\sum _{e\in E}}C(e)\equiv \displaystyle {\sum _{e'\in E'}}C(e') \quad (\text{ mod }\,2m). \end{aligned}$$

(5)

Since the coloring of $K_{M,M}$ uses 2m colors and $C_{2m}$ is rainbow, the edges of $C_{2m}$ exactly use all the colors of $\{0,1,\ldots ,2m-1\}$.

Then

$$\begin{aligned} \displaystyle {\sum _{e\in E}}C(e)+\displaystyle {\sum _{e'\in E'}}C(e')=\displaystyle {\sum _{i=0}^{2m-1}}i. \end{aligned}$$

However, $\displaystyle {\sum _{i=0}^{2m-1}}i=m(2m-1)$. For m odd, $\displaystyle {\sum _{e\in E}}C(e)+\displaystyle {\sum _{e'\in E'}}C(e')$ is odd, which contradicts Eq. (5). Hence, this coloring of $K_{N, N}$ contains no rainbow copy of $C_{2m}$.

For the upper bound, let $N=4m(n-2)+m(m-1)(n-1)+2$. Consider any edge-coloring of $K_{N,N}$ that contains no monochromatic copy of $K_{1,n}$. Then each color appears at most $n-1$ times at each vertex. Denote by $N(C_{2m})$ the number of $C_{2m}$ in $K_{N,N}$ and $N'(C_{2m})$ the number of $C_{2m}$ that are not rainbow colored in $K_{N,N}$.

Then we have

$$\begin{aligned} N(C_{2m})=\left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) \frac{{(m!)}^{2}}{4m}. \end{aligned}$$

(6)

We now estimate the value of $N'(C_{2m})$. If $C_{2m}$ is not rainbow colored, there are at least two edges in the same color. Let $N'_1(C_{2m})$ be the number of $C_{2m}$ containing two adjacent edges in the same color and $N'_2(C_{2m})$ be the number of $C_{2m}$ containing two nonadjacent edges in the same color.

We have

$$\begin{aligned} N'(C_{2m})\le N'_1(C_{2m})+N'_2(C_{2m}). \end{aligned}$$

Suppose the two edges uv and uw are adjacent with the same color. There are 2N choices for u and then N choices for v, in the other partite set. Since at most $n-1$ edges are incident with u in the same color, there are at most $n-2$ choices for w. Since the edge uw might have been chosen first, we have counted each pair of adjacent edges in the same color twice. This makes a total of at most $N^{2}(n-2)$ choices for $\{u,v,w\}$. There are $\left( {\begin{array}{c}N-1\\ m-1\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right)$ ways to choose the remaining vertices from $K_{N,N}$. Along with uv and uw, the chosen $2m-3$ vertices can construct at most $(m-1)!(m-2)!$ even cycles $C_{2m}$ in $K_{N,N}$.

Then

$$\begin{aligned} N'_1(C_{2m}) \le N^{2}(n-2)\left( {\begin{array}{c}N-1\\ m-1\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) (m-1)!(m-2)!. \end{aligned}$$

(7)

Suppose the two edges uv and xy are nonadjacent with the same color. We may assume that u, x are in the same partite set and v, y are in the other partite set. There are N choices for u, N choices for v, and then $N-1$ choices for x. Since at most $n-1$ edges are incident with x in the same color as edge uv, there are at most $n-1$ choices for y. Since the edge xy might have been chosen first, we have counted each pair of nonadjacent edges in the same color twice. This makes a total of at most $\frac{1}{2}N^{2}(N-1)(n-1)$ choices for $\{u,v,x,y\}$. There are $\left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right)$ ways to choose the remaining vertices from $K_{N,N}$. Along with uv and xy, the chosen $2m-4$ vertices can construct at most $\frac{(m-2)!m!}{2m}$ even cycles $C_{2m}$ in $K_{N,N}$.

Then

$$\begin{aligned} N'_2(C_{2m}) \le \frac{1}{4}N^{2}(N-1)(n-1)\left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) (m-2)!(m-1)!. \end{aligned}$$

(8)

By Eqs. (6), (7) and (8), we obtain that

$$\begin{aligned} N'_1(C_{2m})+N'_2(C_{2m})\le & {} N^{2}(n-2)\left( {\begin{array}{c}N-1\\ m-1\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) (m-1)!(m-2)!\\&\quad + \frac{1}{4}N^{2}(N-1)(n{-}1)\left( {\begin{array}{c}N{-}2\\ m{-}2\end{array}}\right) \left( {\begin{array}{c}N-2\\ m-2\end{array}}\right) (m{-}2)!(m{-}1)!\\&=\left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) \frac{m^2(m-1)}{N-1}(n-2)(m-1)!(m-2)!\\&\quad + \frac{1}{4}\left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) \frac{m^2(m-1)^2}{N-1}(n-1)(m-1)!(m-2)!\\&=\left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) (m!)^2\frac{n-2+\frac{1}{4}(m-1)(n-1)}{N-1}\\&=\left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) (m!)^2\frac{n-2+\frac{1}{4}(m-1)(n-1)}{4m(n-2)+m(m-1)(n-1)+1}\\&< \left( {\begin{array}{c}N\\ m\end{array}}\right) \left( {\begin{array}{c}N\\ m\end{array}}\right) \frac{(m!)^2}{4m}\; = \;N(C_{2m}). \end{aligned}$$

So $N'(C_{2m})<N(C_{2m})$ and thus there is a rainbow copy of $C_{2m}$ in $K_{N,N}$. $\square$

5 $BRR(B_{s,t};K_{1,n})$ and $BRR(K_{1,n};B_{s,t})$

In the section, we consider the bounds for bipartite rainbow Ramsey numbers of two graphs where one is a broom and the other is a star. We shall bound the bipartite rainbow Ramsey number $BRR(B_{s,t};K_{1,n})$ and $BRR(K_{1,n};B_{s,t})$.

Theorem 5

For any integers $n,s,t\ge 2$,

$$\begin{aligned}&max\left\{ (n-1)\left( s+\left\lceil \frac{t}{2}\right\rceil -1\right) , 2(n-2)\left( \left\lceil \frac{t}{2} \right\rceil -1\right) \right\} \\&\quad +1\le BRR(B_{s,t};K_{1,n})\le (2s+t-3)(n-1). \end{aligned}$$

Proof of the lower bound in Theorem 5

By Lemma 2 we know that $BRR(B_{s,t};K_{1,n})\ge (n-1)\left( s+\left\lceil \frac{t}{2}\right\rceil -1 \right) +1$ since $B_{s,t}$ is a bipartite graph for the largest partite set has $s+\left\lceil \frac{t}{2}\right\rceil$ vertices. So it suffices to show that $BRR(B_{s,t};K_{1,n})\ge 2(n-2)\left( \left\lceil \frac{t}{2} \right\rceil -1 \right) +1$.

Let $N=2(n-2)\left( \left\lceil \frac{t}{2} \right\rceil -1 \right)$. We give a coloring of $K_{N,N}$ that contains neither a monochromatic copy of $B_{s,t}$ nor a rainbow copy of $K_{1,n}$ as follows. Let V and $V'$ be the two partite sets of $K_{2(n-2),2(n-2)}$. Then we divide the set V into two sets A and B with $A=\{a_1,a_2,\ldots ,a_{n-2}\}$ and $B=\{b_1,b_2,\ldots ,b_{n-2}\}$, and divide the set $V'$ into two sets C and D with $C=\{c_1,c_2,\ldots ,c_{n-2}\}$ and $D=\{d_1,d_2,\ldots ,d_{n-2}\}$. For i, $1\le i\le n-2$, color all edges that join $a_i\in A$ and a vertex in C with color i; color all edges that join $b_i\in B$ and a vertex in D with color $i+n-2$; color all edges that join $c_i\in C$ and a vertex in B with color $i+2(n-2)$; color all edges that join $d_i\in D$ and a vertex in A with color $i+3(n-2)$. The bipartite graph $K_{2(n-2),2(n-2)}$ is colored with $4(n-2)$ colors, and each vertex is incident with exactly $n-1$ different colors. Now replace each vertex in $K_{2(n-2),2(n-2)}$ with $\left\lceil \frac{t}{2} \right\rceil -1$ new vertices to obtain a coloring of $K_{N,N}$. Since there are also exactly $n-1$ colors incident with each vertex in $K_{N,N}$, there is no rainbow copy of $K_{1,n}$. Each color induces a copy of $K_{\left\lceil \frac{t}{2} \right\rceil -1,(\left\lceil \frac{t}{2} \right\rceil -1)(n-2)}$. However, $B_{s,t}$ is a bipartite graph with one partite set containing $\left\lfloor \frac{t}{2} \right\rfloor +1$ vertices and the other partite set containing $s+\left\lceil \frac{t}{2} \right\rceil$ vertices. Hence, this coloring of $K_{N,N}$ contains no monochromatic copy of $B_{s,t}$.$\square$

For the proof of the upper bound for $BRR(B_{s,t};K_{1,n})$, we establish the following lemma by borrowing the method of Eroh and Oellermann [6].

Lemma 8

For any integers $s,t\ge 2$, if a bipartite graph G has average degree at least $2s+t-3$, then G has $B_{s,t}$ as a subgraph.

Proof

Suppose $t=2$, and let G be a bipartite graph with average degree at least $2s-1$. Denote V the vertex set of degree at least $2s-1$. If there is no $B_{s,2}$ as a subgraph in G, then for any $v\in V$, the neighbors of vertex v do not have any neighbors other than v in G. Thus, G consists of a star forest in which each star center vertex has at least $2s-1$ neighbors and a subgraph with maximum degree at most $2s-2$. Then the average degree of G is at most $2s-2$, which produces a contradiction. Hence there is a copy of $B_{s,2}$ in G.

Now we proceed by induction on t. Suppose $t\ge 3$, and let G be a bipartite graph with average degree at least $2s+t-3$. Let H be a minimal subgraph with average degree at least $2s+t-3$ in G in the sense that any proper subgraph in H has average degree less than $2s+t-3$. By the inductive hypothesis, we may assume that H has a subgraph $B_{s,t-1}$ with the vertex set $\{u_1,u_2,\ldots ,u_s,v_1,v_2,\ldots ,v_t\}$ where $\{u_1,u_2,\ldots ,u_s,v_1\}$ is the vertex set of the star $K_{1,s}$ with the center vertex $v_1$ and $\{v_1,v_2,\ldots ,v_t\}$ is the vertex set of the path $P_t$ with endpoints $v_1$ and $v_t$. If the vertex $v_t$ is adjacent to any vertex not in the $B_{s,t-1}$, then it contains $B_{s,t}$. We may assume that $v_t$ is not adjacent to any vertex except the vertices of the broom, so the degree of $v_t$ is at most t / 2 for t even and at most $s+(t-1)/2$ for t odd.

Let A be the vertex set $\{v_2,v_3,\ldots ,v_t\}$ on the path of the broom $B_{s,t-1}$, B be the vertex set $\{v_1,u_1,u_2,\ldots ,u_s\}$ which is the star of the broom $B_{s,t-1}$ and C be the set of remaining vertices in H. Thus, the vertex set $V(H)=A\cup B\cup C$. For two vertex sets U and V, we denote |E(U, V)| the number of edges between U and V. Then we prove the following two assertions.

Claim 1

For t odd, $|E(A,C)|\ge \frac{t-1}{2} \left( s+\frac{t-1}{2}-3\right) +1$.

Suppose that $|E(A,C)|\le \frac{t-1}{2} \left( s+\frac{t-1}{2}-3\right)$. Based on the parity of t, |E(A)| is at most $\frac{(t-1)^{2}}{4}$ for t odd and $\frac{t(t-2)}{4}$ for t even. |E(A, B)| is at most $\frac{t-1}{2}(s+1)$ for t odd and $\frac{t}{2}(s+1)-s$ for t even.

Since the average degree of H

$$\begin{aligned} d(H)=\frac{2(|E(B\cup C)|+|E(A)|+|E(A,C)|+|E(A,B)|)}{|V(H)|}, \end{aligned}$$

we have

$$\begin{aligned} d(H)\le \frac{d(B\cup C)|V(B\cup C)|+\frac{(t-1)^{2}}{2}+(t-1)(s+\frac{t-1}{2}-3)+(t-1)(s+1)}{|V(H)|}. \end{aligned}$$

Since $d(H)\ge (2s+t-3)$, we have

$$\begin{aligned} 2s+t-3\le d(B\cup C)\frac{|V(B\cup C)|}{|V(H)|}+(2s+t-3)\frac{|V(A)|}{|V(H)|}. \end{aligned}$$

Since $|V(H)|=|V(A)|+|V(B\cup C)|$, we have $d(B\cup C)\ge 2s+t-3$. Thus we can obtain a proper subgraph of H with average degree at least $2s+t-3$, which contradicts our choice of H, completing the proof of Claim 1.

Claim 2

If $d_{H}(v_t)= s+\frac{t-1}{2}$ for t odd, then we have a copy of $B_{s,t}$ as a subgraph in H.

Since $d_{H}(v_t)=s+\frac{t-1}{2}$, then $v_t$ is adjacent to $\{u_1,u_2,\ldots ,u_s,v_2,v_4,\ldots ,v_{t-1}\}$ for t odd. Let $A_1=\{v_2,v_4,\ldots ,v_{t-1}\}$ and $A_2=\{v_3,v_5,\ldots ,v_{t-2}\}$. For any $v_i\in A_1$, if $d_{C}(v_i)\ge s$, $v_i$ and its neighbors can induce a copy of $K_{1,s}$ in H. Along with the path $P_{t+1}=v_{i+1}v_{i+2}\ldots v_{t}u_1v_1v_2\ldots v_{i-1}$, we can have a copy of $B_{s,t}$. Thus, we may assume that $d_{C}(v_i)\le s-1$ for $v_i\in A_1$, then $|E(A_1,C)|\le (s-1)\frac{t-1}{2}$. Since $d_{C}(v_t)=0$, by Claim 1, we can find

$$\begin{aligned} |E(A_2,C)|=|E(A,C)|-|E(A_1,C)|\ge \frac{(t-3)^{2}}{4}. \end{aligned}$$

Case 1 $t\ge 5$. Then there is at least one edge between $A_2$ and C. Assume that this edge joins $v_{i_0}\in A_2$ to the vertex $w\in C$. Since $i_0$ is odd, the vertex $v_t$ must be adjacent to $v_{i_0-1}$. Hence $v_1v_2\ldots v_{i_0-1}v_tv_{t-1}v_{t-2}\ldots v_{i_0+1}v_{i_0}w$ forms a copy of $P_{t+1}$. Along with the copy of $K_{1,n}$ in B, we again have a copy of $B_{s,t}$.

Case 2 $t=3$. From Claim 1 and the previous case, we know that $|E(A,C)|=d_C(v_2)\ge s-1$ for $t=3$. However, $d_C(v_2)\le s-1$, otherwise we have a copy of $B_{s,3}$. Thus, we may assume that $d_C(v_2)=s-1$. Let the neighbors of vertex $v_2$ in C be $w_1,w_2,\ldots ,w_{s-1}$. Since $v_2$ is also adjacent to $v_1$ and $v_3$, we have $d_H(v_2)=s+1$.

If $d_C(v_1)\ge 1$, let w be the vertex in C which is adjacent to $v_1$. Then the vertex set $\{v_1,u_2,u_3,\ldots ,u_s,w\}$ can induce a copy of $K_{1,s}$. Along with the path $P_4=v_1u_1v_3v_2$, we have a copy of $B_{s,3}$. So we may assume that $d_C(v_1)=0$.

If $u_1$ is adjacent to some vertex $w'$ in $C {\setminus } \{w_1,w_2,\ldots ,w_{s-1}\}$, the vertex set $\{v_2,v_3,w_1,w_2,\ldots ,w_{s-1}\}$ induces a copy of $K_{1,s}$. Along with the path $P_4=v_2v_1u_1w'$, we again have a copy of $B_{s,3}$. Hence, we assume that $d_C(u_1)\le s-1$.

Let $A'$ denote the vertex set $\{u_1,v_1,v_2,v_3\}$, $B'$ denote the vertex set $\{u_2,u_3,\ldots ,u_s\}$. Then we have

$$\begin{aligned} d(H)\le \frac{d(B'\cup C)|V(B'\cup C)|+2|E(A')|+2|E(A',C)|+2|E(A',B')|}{|V(H)|}. \end{aligned}$$

Since $d(H)\ge 2s$, $|E(A')|=4$, $|E(A',C)|\le 2s-2$ and $|E(A',B')|=2s-2$, we have

$$\begin{aligned} 2s\le d(B'\cup C)\frac{|V(B'\cup C)|}{|V(H)|}+2s\frac{|V(A')|}{|V(H)|}. \end{aligned}$$

Since $|V(H)|=|V(A')|+|V(B'\cup C)|$, we have $d(B'\cup C)\ge 2s$. Then we can obtain a proper subgraph of H with average degree at least 2s, which again contradicts our choice of H, completing the proof of Claim 2.

We continue the proof of Lemma 8. From Claim 2, we may assume that $d_{H}(v_t)\le s+\frac{t-1}{2}-1$, including the case that t is even. We have

$$\begin{aligned} d(H {\setminus } \{v_t\})\ge & {} \frac{2(|E(H)|-(s+\frac{t-1}{2}-1))}{|V(H)|-1}\;=\; \frac{2|E(H)|-(2s+t-3)}{|V(H)|-1}\\\ge & {} \frac{(2s+t-3)|V(H)|-(2s+t-3)}{|V(H)|-1}\;=\; 2s+t-3. \end{aligned}$$

Thus, we have a proper subgraph of H with average degree at least $2s+t-3$, which again contradicts our choice of H. There must be some subgraph $B_{s,t}$ in H, so in G.$\square$

Proof of the upper bound in Theorem 5

Let $N=(2s+t-3)(n-1)$. Consider any edge-coloring of $G=K_{N,N}$. Suppose this edge-coloring of $K_{N,N}$ contains no rainbow copy of $K_{1,n}$. Let $G_c$ be the subgraph induced by all edges in color c, $V_c$ the set of vertices incident with edges of color c, and $C_v$ the set of colors incident with vertex v. We denote $d_c(v)$ the degree of vertex v in $G_c$. Then for any v, we have $|C_v|\le n-1$, and

$$\begin{aligned} d(G_c)=\frac{\sum _{v\in V_c}d_c(v)}{|V_c|}. \end{aligned}$$

So

$$\begin{aligned} \displaystyle {\sum _{c}}\frac{\sum _{v\in V_c}d_c(v)}{|V_c|}\ge \frac{\displaystyle {\sum _{c}}\displaystyle {\sum _{v\in V_c}}d_c(v)}{\displaystyle {\sum _{c}}|V_c|} = \frac{\displaystyle {\sum _{v\in V(G)}}d(v)}{\displaystyle {\sum _{v\in V(G)}}|C_v|} \ge \frac{2N^{2}}{2N(n-1)}= 2s+t-3. \end{aligned}$$

Thus, there must be some color c such that $d(G_c)\ge 2s+t-3$. By Lemma 8, we can obtain a copy of $B_{s,t}$ in $G_c$, and, hence we have a monochromatic copy of $B_{s,t}$ in G. $\square$

Now we determine the bounds for $BRR(K_{1,n};B_{s,t})$. For $t=1$, $B_{s,t}=K_{1,s+1}$ and we know that $BRR(K_{1,n};B_{s,1})=(n-1)s+1$, see [6]. Now we show the value of $BRR(K_{1,n};B_{s,2})$.

Lemma 9

For any positive integers n and s,

$$\begin{aligned} BRR(K_{1,n};B_{s,2})=(n-1)(s+1)+1. \end{aligned}$$

Proof

By Lemma 2, we know that $BRR(K_{1,n};B_{s,2})\ge (n-1)(s+1)+1$. Let $N=(n-1)(s+1)+1$. Consider an edge-coloring of $K_{N,N}$ with any number of colors. If there is no monochromatic copy of $K_{1,n}$, then at least $s+2$ colors are present at each vertex. We can take a rainbow copy of $K_{1,s+1}$ from the coloring $K_{N,N}$. Let u and v denote the center vertex and any other vertex of this rainbow $K_{1,s+1}$, respectively. Then there are at least $s+2$ colors incident with v.

If at least $s+2$ colors are incident with v in $K_{N,N}{\setminus }{\{u\}}$, there is at least one edge incident with v in some color that does not yet appear in the rainbow $K_{1,s+1}$. If $s+1$ colors are incident with v in $K_{N,N}{\setminus }{\{u\}}$, then the color of edge uv does not appear in these $s+1$ colors, so we can obtain at least one edge incident with v in some color that does not yet appear in the rainbow $K_{1,s+1}$. Along with the $K_{1,s+1}$, we have a rainbow $B_{s,2}$. $\square$

The next theorem provides bounds for $BRR(K_{1,n};B_{s,t})$.

Theorem 6

For any positive integers n, s and t,

$$\begin{aligned} (n-1)(s+t-1)+1\le BRR(K_{1,n};B_{s,t})\le (n-1)(s+t-1)+s+\frac{t+1}{2}. \end{aligned}$$

Proof

The assertion is obvious for $n=1$, so we assume $n\ge 2$. Since $BRR(K_{1,n};B_{s,1})=(n-1)s+1$, the assertion is also trivial for $t=1$. Then we suppose $t\ge 2$.

The lower bound follows from Lemma 2. For the upper bound, let $N=(n-1)(s+t-1)+s+(t+1)/2$. For $t=2$, from Lemma 9 we know that $BRR(K_{1,n};B_{s,2})\le (n-1)(s+1)+s+1$. We proceed by induction on t. Consider an edge-coloring of $K_{N,N}$ that does not contain a monochromatic copy of $K_{1,n}$. We may assume that there is a rainbow copy of $B_{s,t-1}$. Let F be the rainbow copy of $B_{s,t-1}$ in $K_{N,N}$ and V(F) be the vertex set of F. Denote u and v the center of $K_{1,s}$ and the another endpoint of path $P_t$ in F. To prove there is a rainbow copy of $B_{s,t}$, we consider the parity of t.

Case 1 If t is even, u and v are in the different partite sets of $K_{N,N}$. Then v has $N-t/2$ neighbors in $K_{N,N}{\setminus } V(F)$. Since there is no monochromatic copy of $K_{1,n}$, there are at least

$$\begin{aligned} \left\lceil \frac{(n-1)(s+t-1)+s+(t+1)/2-t/2}{n-1} \right\rceil \ge s+t \end{aligned}$$

colors incident with v. There are $s+t-1$ colors in F. Thus, at least one edge incident with v in some color does not yet appear in the rainbow F. We obtain a rainbow copy of $B_{s,t}$ in $K_{N,N}$ by combining this edge and the broom F.

Case 2 If t is odd, u and v are in the same partite set of $K_{N,N}$. Then v has $N-s-(t-1)/2$ neighbors in $K_{N,N}{\setminus } V(F)$. Since there is no monochromatic $K_{1,n}$, there are at least

$$\begin{aligned} \left\lceil \frac{(n-1)(s+t-1)+s+(t+1)/2-s-(t-1)/2}{n-1} \right\rceil \ge s+t \end{aligned}$$

colors incident with v, which gives a rainbow copy of $B_{s,t}$ similarly. $\square$