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 |