- Series
- School of Mathematics Colloquium
- Time
- Tuesday, March 13, 2012 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Jeff Kahn – Mathematics, Rutgers University – jkahn@math.rutgers.edu
- Organizer
- Prasad Tetali
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.