Multicolor Ramsey Numbers of Bipartite Graphs and Large Books

Abstract

For graphs G and H, the Ramsey number $r_{k+1}(G;H)$ is defined as the minimum N such that any edge-coloring of $K_N$ by $k+1$ colors contains either a monochromatic G in the first k colors or a monochromatic H in the last color. A book $B^{(m)}_{n}$ is a graph that consists of n copies of $K_{m+1}$ sharing a common $K_m$. We shall give upper bounds for $r_{k+1}(K_{t,s};B^{(m)}_n)$ and $r_{k+1}(C_{2t};B^{(m)}_n)$, some of which are sharp up to the sub-linear term asymptotically.

1 Introduction

For graphs $G_1,\dots ,G_k$, the Ramsey number $r_k(G_1,\dots ,G_k)$ is defined as the minimum N such that if edges of $K_N$ are colored by k colors, then there is a monochromatic $G_i$ in a color i with $1\le i\le k$. We shall write $r_{k+1}(G,\dots ,G,G_{k+1})$ as $r_{k+1}(G;G_{k+1})$ in short, and write two color Ramsey number $r_2(G_1,G_2)$ as $r(G_1,G_2)$, and r(G, G) as r(G).

Call graph $B^{(m)}_n$ a book that consists of n copies of $K_{m+1}$ that share a common $K_m$. As usual, we write $B^{(2)}_n$ as $B_n$. Book graph plays an important role in graph Ramsey theory. It was shown by Rousseau and Sheehan [10] that $r(B_n)=4n+2$ for infinitely many n, and $r(B_m,K_n)$ was bounded from above by Li and Rousseau [6]. Moreover, Conlon [3] obtained $r(B^{(m)}_n)\sim 2^m n$ as $n\rightarrow \infty$.

For large n, complete bipartite graph $K_{m,n}$ and book $B_n^{(m)}$ seem to look like each other, and the Ramsey numbers involving them are known to be close in some cases. Chung and Graham [2] established

$$\begin{aligned} r_k(K_{m,n})\le (n-1)(k+k^{1/m})^m \end{aligned}$$

for $k\ge 2, n\ge m\ge 2$, and

$$\begin{aligned} r_k(K_{2,n})\le (n-1)k^2+k+2. \end{aligned}$$

Recently, Wang et al. obtained the following result. For positive functions f(n) and g(n), we write $f(n)=o(g(n))$ if $f(n)/g(n)\rightarrow 0$ as $n\rightarrow \infty$.

Lemma 1

[11] Let integers $k\ge 1$ and $s\ge t\ge m\ge 1$. Then

$$\begin{aligned} r_{k+1}(K_{t,s}; K_{m,n})\le n + (1+o(1))(s-t+1)^{1/t} k m n^{1-1/t} \end{aligned}$$

(1)

as $n\rightarrow \infty$. There are infinitely many n such that (1) becomes an equality for $r_{k+1}(K_{2,s}; K_{1,n})$, $r_{k+1}(K_{3,3}; K_{1,n})$, $r(K_{2,s}, K_{2,n})$ and $r(K_{3,3}, K_{m,n})$ for $m \le 3$.

Since $r_{k+1}(G;K_{m,n})\le r_{k+1}(G;B^{(m)}_n)$, we shall generalize Lemma 1 by replacing $K_{m,n}$ with $B^{(m)}_n$.

Theorem 1

Let $s\ge t\ge 2$ and $k,m\ge 1$ be fixed integers. If n is large, then

$$\begin{aligned} r_{k+1}(K_{t,s};B_n^{(m)})\le n+ (1+o(1)) (s-t+1)^{1/t} k m n^{1-1/t}. \end{aligned}$$

(2)

Corollary 1

Let $s\ge 2$ and $m\ge 1$ be fixed integers. Then, there are infinitely many n such that

$$\begin{aligned} r(K_{2,s}, B_n^{(m)})= n + (1+o(1)) m \sqrt{(s-1) n}, \end{aligned}$$

and $r(K_{2,s}, K_{m,n})= n + (1+o(1)) m \sqrt{(s-1) n}$ as such $n\rightarrow \infty$.

Corollary 2

Let $m\ge 1$ be an integer. Then, there are infinitely many n such that

$$\begin{aligned} r(K_{3,3}, B_n^{(m)})= n + (1+o(1)) m n^{2/3}, \end{aligned}$$

and $r(K_{3,3}, K_{m,n})= n + (1+o(1)) m n^{2/3}$ as such $n\rightarrow \infty$.

Ramsey numbers involving cycles and large stars have attracted much attention. Parsons [9] obtained

$$\begin{aligned} r(C_4,K_{1,n})\le n+\lceil \sqrt{n}\,\rceil +1 \end{aligned}$$

for any $n\ge 2$, and the equality holds for infinitely many n, and if q is a prime power, then $r(C_4,K_{1,q^2})=q^2+q+1$ and $r(C_4,K_{1,q^2+1})=q^2+q+2$.

Zhang, Chen and Cheng [13] showed that

$$\begin{aligned} r_{k+1}(C_4; K_{1,n}) \le n+ \lceil k\sqrt{n +(k^2+2k-3)/4}\rceil +\frac{k(k+1)}{2}, \end{aligned}$$

and $r_3(C_4;K_{1,n})=n+\sqrt{4n+1}+3$ for infinitely many n.

Liu and Li [8] determined $r(C_{2t+1}, B^{(m)}_{n})=2(m+n-1)+1$ for $t,m\ge 1$, and Lin and Peng [7] obtained $r(C_n,B^{(m)}_n)=(m+o(1))n$ as $m\ge 3$ and $n\rightarrow \infty$.

We shall investigate the behavior of $r_{k+1}(C_{2t};B^{(m)}_{n})$ for large n as follows.

Theorem 2

Let k, t and m be positive integers. If n is large, then

$$\begin{aligned} r_{k+1}(C_{2t};B^{(m)}_{n})\le n+ (1+o(1))c_t k m n^{1/t}, \end{aligned}$$

where $c_t>0$ is a constant depends on t only. Furthermore, for each $t\in \{2,3,5\}$, there are infinitely many n such that

$$\begin{aligned} r_{k+1}(C_{2t};B^{(m)}_{n})) \ge n+ (1-o(1))c k n^{1/t} \end{aligned}$$

for such n if n is large, where $c=c(t)>0$ is a constant.

2 Proofs of Main Results

For a graph G, denote by v(G) and e(G) the numbers of vertices and edges of G, respectively. A graph G is said to be H-free if G contains no H as a subgraph. The Turán number ex(n, H) of H is defined as the maximum e(G) of an H-free graph G of order n.

A well known result of Kövari, Sós and Turán [5] tells us

$$\begin{aligned} ex(N,K_{t,s})\le \frac{1}{2} \big [(s-1)^{1/t}N^{2-1/t}+(t-1)N\big ]\;\; (s\ge t\ge 1). \end{aligned}$$

Füredi [4] showed

$$\begin{aligned} ex(N,K_{t,s})\le \frac{1}{2}\big [(s-t+1)^{1/t} N^{2-1/t}+tN+tN^{2-2/t}\big ] \end{aligned}$$

for $s\ge t\ge 1$. Thus we know that if $s\ge t\ge 2$, then

$$\begin{aligned} ex(N,K_{t,s})\le (1+o(1))\frac{1}{2}(s-t+1)^{1/t} N^{2-1/t} \end{aligned}$$

(3)

as $N\rightarrow \infty$. For even cycles $C_{2t}$, Bondy and Simonovits [1] proved for any $t\ge 2$,

$$\begin{aligned} ex(N,C_{2t})\le c_t N^{1+1/t} \end{aligned}$$

(4)

for large N, where $c_t>0$.

We also need the following result from [11], for which we can replace the condition $ex(N,H)\sim cN^{2-\eta }$ with $ex(N,H)\ge cN^{2-\eta }$ from the proof as we need a lower bound for $r_{k+1}(H;K_{1,n})$ only. Let $\delta (G)$ and $\varDelta (G)$ be the minimum and maximum degree of graph G, respectively.

Lemma 2

[11] Let H be a bipartite graph with $ex(N,H)\ge cN^{2-\eta }$ as $N\rightarrow \infty$, where c and $\eta$ are positive constants. If there are extremal graphs $G_N$ of order N for ex(N, H) such that $\delta (G_N)\sim \varDelta (G_N)$ as $N\rightarrow \infty$, then

$$\begin{aligned} r_{k+1}(H; K_{1,n})\ge n + (1-\epsilon )2kc n^{1-\eta } \end{aligned}$$

for large n, where $\epsilon >0$.

In following proofs, when we color the edges of $K_N$ by $k+1$ colors, we shall write the monochromatic graph induced by edges in color i as $G_i$ for $1\le i\le k+1$. For a vertex v, we denote by $d_i(v)$ as the degree of v in the graph $G_i$, and thus $\sum _{i=1}^{k+1}d_i(v)=N-1$ for any v.

We shall not distinguish $\lceil x\rceil$ and $\lfloor x\rfloor$ from x for large x as the differences are negligible for asymptotic computation.

Proof of Theorem 1

For any $\epsilon >0$, let

$$\begin{aligned} \ell _m= (1+\epsilon ) k m (s-t+1)^{1/t}n^{1-1/t} \end{aligned}$$

and $N_m=n+\ell _m$. We shall show

$$\begin{aligned} r_{k+1}(K_{t,s};B_n^{(m)})\le N_m = n+ \ell _m \end{aligned}$$

(5)

for all large n by induction on m.

To simplify the proof, we shall start at $m=0$ instead of $m=1$, in which $K_{0,n}$ is admitted as ${\overline{K}}_n$ that consists of n vertices without any edge.

For the case $m=0$, the claimed upper bound follows as any graph of order $N_0=n$ contains ${\overline{K}}_n$ as a subgraph.

Next, we assume that (5) holds for any $m\ge 0$, and we shall show that it holds for $m+1$.

Consider an edge coloring of $K_{N_{m+1}}$ by $k+1$ colors. We shall show that there is a $B_n^{(m+1)}$ in $G_{k+1}$ or a $K_{t,s}$ in some $G_i$ for $1\le i\le k$.

If there is a vertex v such that $d_{k+1}(v)\ge r_{k+1}(K_{t,s};B_n^{(m)})$, then the neighborhood of v in $G_{k+1}$, whose edges are colored by $k+1$ colors, contains a subgraph $B_n^{(m)}$ in color $k+1$, hence that and v form a subgraph $B_n^{(m+1)}$ of $G_{k+1}$, and thus we are done. So we may assume that for each vertex v,

$$\begin{aligned} d_{k+1}(v)\le r_{k+1}(K_{t,s};B_n^{(m)})-1 \le n+\ell _m -1, \end{aligned}$$

in which the second inequality comes from induction hypothesis. So we have

$$\begin{aligned} e(G_{k+1}) =\frac{1}{2} \sum _{v} d_{k+1}(v) \le \frac{1}{2}N_{m+1} (n+\ell _m -1). \end{aligned}$$

Hence

$$\begin{aligned} \sum _{i=1}^k e(G_i)= & {} \left( {\begin{array}{c}N_{m+1}\\ 2\end{array}}\right) -e(G_{k+1}) \ge \frac{N_{m+1}}{2} (N_{m+1}-n-\ell _m) \\= & {} \frac{N_{m+1}}{2}(\ell _{m+1}-\ell _m), \end{aligned}$$

where

$$\begin{aligned} \ell _{m+1}-\ell _m= & {} \Big [(1+\epsilon )(m+1) -(1+\epsilon )m \Big ]k(s-t+1)^{1/t}n^{1-1/t} \\= & {} (1+\epsilon ) k (s-t+1)^{1/t} n^{1-1/t} \\\ge & {} \big (1+\frac{\epsilon }{2}\big )k(s-t+1)^{1/t} N_{m+1}^{1-1/t} \end{aligned}$$

as $n\sim N_{m+1}$ for large n. Therefore, there is a $G_j$ with $1\le j\le k$ such that

$$\begin{aligned} e(G_j)\ge \frac{1}{k} \sum _{i=1}^k e(G_i)\ge \frac{1}{2} \big (1+\frac{\epsilon }{2}\big )(s-t+1)^{1/t} N_{m+1}^{2-1/t}>ex(N_{m+1},K_{t,s}), \end{aligned}$$

where the last inequality comes from (3). Thus $G_j$ contains a $K_{t,s}$, and then we get the desired upper bound. $\square$

Proof of Corollary 1

Lemma 7 in [11] says that

$$\begin{aligned} r(K_{2,s},K_{m,n})\ge n+(1+o(1))m\sqrt{(s-1)n} \end{aligned}$$

for any $s\ge 2$, $m\ge 1$, and infinitely many n, which and Theorem 1 for $k=1$ and $t=2$ imply the desired statements since $r(K_{2,s};B_n^{(m)})\ge r(K_{2,s};K_{m,n})$. $\square$

Proof of Corollary 2

Lemma 9 in [11] says that

$$\begin{aligned} r(K_{3,3},K_{m,n})\ge n+(1+o(1))mn^{2/3} \end{aligned}$$

for any $m\ge 1$ and infinitely many n, which and Theorem 1 for $k=1$ imply the desired statements since $r(K_{3,3};B_n^{(m)})\ge r(K_{3,3};K_{m,n})$. $\square$

Proof of Theorem 2

For any $\epsilon >0$, let

$$\begin{aligned} \ell _m = (1+\epsilon )c_tkm n^{1/t} \end{aligned}$$

and $N_m=n+\ell _m$, where $c_t>0$ is the constant in (4). We shall show

$$\begin{aligned} r_{k+1}(C_{2t};B_n^{(m)}) \le N_m =n+\ell _m \end{aligned}$$

(6)

for all large n. The proof is similar to that for Theorem 1 by induction on $m\ge 0$, and we go to the inductive step directly to show (6) for case $m+1$ by considering an edge coloring of $K_{N_{m+1}}$ with $k+1$ colors, in which $G_{k+1}$ contains no $B_n^{(m)}$.

The similar analysis and induction hypothesis imply

$$\begin{aligned} \sum _{i=1}^k e(G_i) \ge \left( {\begin{array}{c}N_{m+1}\\ 2\end{array}}\right) -e(G_{k+1}) \ge \frac{N_{m+1}}{2}(\ell _{m+1}-\ell _m), \end{aligned}$$

where

$$\begin{aligned} \ell _{m+1}-\ell _m \ge \big (1+\frac{\epsilon }{2}\big ) c_t k N_{m+1}^{1/t}. \end{aligned}$$

So some $G_j$ with $1\le j\le k$ has $e(G_j)> ex(N_{m+1},C_{2t})$ and $G_j$ contains $C_{2t}$.

Next, for $t\in \{2,3,5\}$, we shall show that there are infinitely many n such that

$$\begin{aligned} r_{k+1}(C_{2t};B^{(m)}_{n}) \ge n+ (1-\epsilon )c k n^{1/t} \end{aligned}$$

for these n. To this end, the starting point is the result of Wenger [12] as

$$\begin{aligned} ex(n,C_{2t}) \ge c n^{1+1/t} =c n^{2-(t-1)/t}, \end{aligned}$$

where $c=c(t)>0$ is a constant. Thus Lemma 2 implies

$$\begin{aligned} r_{k+1}(C_{2t};K_{1,n})\ge n+ (1-o(1))2ck n^{1-(t-1)/t} = n+ (1-o(1))2ck n^{1/t}, \end{aligned}$$

and it follows by $r_{k+1}(C_{2t};B_n^{(m)})\ge r_{k+1}(C_{2t};K_{1,n})$ as required. $\square$