The Probabilistic Method is a lasting legacy of the late Paul Erdös. We give two examples - both problems first formulated by Erdös in the 1960s with new results in the last few years and both with substantial open questions. Further in both examples we take a Computer Science vantagepoint, creating a probabilistic algorithm to create the object (coloring, packing respectively) and showing that with positive probability the created object has the desired properties.

• Given m sets each of size n (with an arbitrary intersection pattern) we want to color the underlying vertices Red and Blue so that no set is monochromatic. Erdös showed this may always be done if m < 2^(n-1), we give a recent argument of Srinivasan and Radhukrishnan that extends this to m < c.2^n.sqrt(n/ln n). One first colors randomly and then recolors the blemishes with a clever random sequential algorithm.
• In a universe of size N we have a family of sets, each of size k, such that each vertex is in D sets and any two vertices have only o(D) common sets. Asymptotics are for fixed k with N,D --> oo. We want an asymptotic packing, a subfamily of ~ N/k disjoint sets. Erdös and Hanani conjectured such a packing exists (in an important special case of asymptotic designs) and this conjecture was shown by Rödl. We give a recent simple proof of the speaker that analyzes the random greedy algorithm.

January 15th "The Phase Transition for Random Graphs"

January 17th "The Strange Logic of Random Graphs"