3:00 p.m., Friday (April 29, 2005)
West Mall Annex 110 (PIMS Facility)
Probabilistic reasoning and Ramsey Theory
Abstract: "Ramsey Theory" refers to a large body of deep results in mathematics
concerning the partition of large collections. Its underlying philosophy
is captured succinctly by the statement that "In a large system complete
disorder is impossible". Since the publication of the seminal paper of
Ramsey in 1930, this subject has grown with increasing vitality, and is
currently among the most active areas in Combinatorics. An important
factor in the development of Ramsey Theory was the successful application
of the so-called "Probabilistic Method". This method was initiated more
than fifty years ago by Paul Erdos, and became one of the most powerful
and widely used tools in Discrete Mathematics.
In this talk I will describe some classical results of Ramsey Theory
together with recent progress on some old questions of Erdos which was
made using probabilistic arguments. I will also discuss the problem of
converting existence arguments into deterministic constructions, in
particular, the recent explicit constructions of Bipartite Ramsey graphs.
Refreshments will be served at 2:45 p.m. in the PIMS 1st floor lounge.