UW Combinatorics Seminar

77 Years of Ramsey $R(3,k)$ (and Counting!)

Joel Spencer

New York University

May 21, 4:00pm
Padelford C-401

refreshments at 3:30pm
Pre-Seminar at 2:30pm in Padelford C-401

ABSTRACT 

The Ramsey Number $R(3,k)$ is that least number $n$ (dependent on $k$) so that {\em any} triangle-free graph on $n$ vertices {\em must} contain an independent set of $k$ vertices. An examination of (appropriately defined) random graphs and random processes plays a key role in finding the asymptotics of $R(3,k)$. Our story takes us from three youngsters, George Szekeres, Esther Klein and Paul Erdos, in the winter of 1931/2 through Greenwood, Gleason, Graver, Yackel, Ajtai, Komlos, Szemeredi, Kim, Lovasz, Winkler, Suen (to name a few!) to very recent work of Bohman.


Speaker's Contact Info: http://cs.nyu.edu/cs/faculty/spencer/


Return to seminar home page

Combinatorics Seminar, Mathematics Department, University of Washington, billey@math.washington

Page loaded on May 06, 2008 at 09:59 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.