Mar 23, 4:30pm, Wean 7500

Jeff Kahn, Rutgers

Thresholds and expectation thresholds

Jeff Kahn, Rutgers

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.