A Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t)

TitleA Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t)
Publication TypeTechnical Report
Year of Publication1989
AuthorsCleve R, Dagum P
Other Numbers508
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.

URLhttp://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