𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multicolor bipartite Ramsey number of C4 and large Kn, n

✍ Scribed by Qizhong Lin; Yusheng Li


Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
92 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis


Let br k (C 4 ; K n,n ) be the smallest N such that if all edges of K N,N are colored by k +1 colors, then there is a monochromatic C 4 in one of the first k colors or a monochromatic K n,n in the last color. It is shown that br k (C 4 ; K n,n ) = (n 2 / log 2 n) for k β‰₯ 3, and br 2 (C 4 ; K n,n ) β‰₯ c(n log log n / log 2 n) 2 for large n. The main part of the proof is an algorithm to bound the number of large K n,n in quasi-random graphs.