Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs |
| |
Authors: | John Lenz Dhruv Mubayi |
| |
Institution: | DEPARTMENT OF MATHEMATICS, STATISTICS, AND COMPUTER SCIENCE, UNIVERSITY OF ILLINOIS AT CHICAGO, CHICAGO, ILLINOIS |
| |
Abstract: | Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c1 and c2 are absolute constants. |
| |
Keywords: | Ramsey theory graph eigenvalues graph spectrum |
|
|