A Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t)
Title | A Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t) |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Cleve, R., & Dagum P. |
Other Numbers | 508 |
Abstract | We present a feasibly constructive proof that R(3,t) > 5((t-1)/2)(superscript (log4/log3)) Element Omega (t(superscript 1.26)). This is, as far as we know, the first constructive superlinear lower bound for R(3,t). Also, our result yields the first feasible method for constructing triangle-free k-chromatic graphs that are polynomial-size in k. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-009.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-009 |
Abbreviated Authors | R. Cleve and P. Dagum |
ICSI Publication Type | Technical Report |