Colloquium Schedule for Spring 1999 |

The Ramsey number R(3,t) has asymptotic order of magnitude t2/log t


Jeong Han Kim
Microsoft Research





The Ramsey number R(s,t) is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. In this talk, we describe a dynamic probabilistic method which is used to settle an old problem on R(3,t). Namely, R(3,t) has asymptotic order of magnitude t2/log t.