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.