CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Jeff Kahn
Rutgers
Title: Thresholds and expectation thresholds

Abstract: Thresholds for increasing properties are a central concern in probabilistic combinatorics and elsewhere. (An increasing property, say F, is a superset-closed family of subsets of some (here finite) set X; the threshold question for such an F asks, roughly, about how many random elements of X should one choose to make it likely that the resulting set lies in F? For example: about how many random edges from the complete graph K_n are typically required to produce a Hamiltonian cycle?) We'll discuss recent progress and lack thereof on a few threshold-type questions, and try to say something about a ludicrously general conjecture of G. Kalai and the speaker to the effect that there is always a pretty good naive explanation for a threshold being what it is.

Date: Friday, March 23, 2012
Time: 4:30 pm
Location: Wean Hall 7500
Submitted by:  Loh