Multicolor bipartite Ramsey number of C4 and large Kn,n |
| |
Authors: | Qizhong Lin Yusheng Li |
| |
Institution: | 1. College of Mathematics and Computer Science Fuzhou University, Fuzhou 350108, China;2. Department of Mathematics Tongji University, Shanghai 200092, China |
| |
Abstract: | Let brk(C4;Kn, n) be the smallest N such that if all edges of KN, N are colored by k + 1 colors, then there is a monochromatic C4 in one of the first k colors or a monochromatic Kn, n in the last color. It is shown that brk(C4;Kn, n) = Θ(n2/log2n) for k?3, and br2(C4;Kn, n)≥c(n n/log2n)2 for large n. The main part of the proof is an algorithm to bound the number of large Kn, n in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011 |
| |
Keywords: | bipartite Ramsey number cycle asymptotic bound |
|
|