Extremal and Probabilistic Combinatorics

04/13/2010 - 12:15pm
04/13/2010 - 1:10pm
Choongbum Lee (UCLA)

Extremal Combinatorics studies the maximum or minimum size of discrete structures (e.g., graphs, set systems) with certain properties. Many questions in this area are motivated by problems in analysis, number theory, probability, theoretical computer science, etc., and numerous problems which seem to be purely combinatorial can only be proved by relying on tools from algebra, analysis, topology, probability and other areas. Moreover, the tools that were developed for one problem turn out to have striking applications in other problems as well. The most successfully developed tool among them is the so-called probabilistic method. Probabilistic Combinatorics, on one hand is the study of this universal framework, which can be potentially applied to any combinatorial problem, and on the other refers to the study of random objects such as the Erdos-Renyi random graphs.

There are now fields of Graph Theory and Combinatorics that combine both extremal and probabilistic problems in the most natural ways. Extremal Theory of Random Graphs is one such subject, where we study the typical behavior of basic graph theoretic parameters over the probability space of random graphs. In this talk, I will give a brief introduction to the two topics mentioned above, and then discuss some recent developments in this new field.

Joint work with Hao Huang, Michael Krivelevich, Wojciech Samotij, and Benny Sudakov.

Millikan 208 (Pomona College)