An Explicit Construction for a Ramsey Problem |
| |
Authors: | Email author" target="_blank">Dhruv?MubayiEmail author |
| |
Institution: | (1) Department of Mathematics, Statistics, & Computer Science, University of Illinois at Chicago 322 Science & Engineering Offices (SEO) m/c 249, 851 S. Morgan Street, Chicago, IL 60607-7045, USA |
| |
Abstract: | An explicit coloring of the edges of Kn is constructed such that every copy of K4 has at least four colors on its edges. As n , the number of colors used is n1/2+o(1). This improves upon the previous bound of O(n2/3) due to Erds and Gyárfás obtained by probabilistic methods. The exponent 1/2 is optimal, since it is known that at least (n1/2) colors are required in such a coloring.The coloring is related to constructions giving lower bounds for the multicolor Ramsey number rk(C4). It is more complicated however, because of restrictions imposed on interactions between color classes.* Research supported in part by NSF Grant No. DMS–9970325. |
| |
Keywords: | 05C35 05C55 05D10 |
本文献已被 SpringerLink 等数据库收录! |
|