Jeff Kahn, Rutgers University

Abstract

Shamir's Problem (circa 1980) asks: for fixed r at least 3 and n a (large) multiple of r, how large should M be so that M random r-subsets of {1, ... ,n} are likely to contain a perfect matching (i.e., n/r disjoint r-sets)? About ten years ago Johansson, Vu and I proved the natural conjecture that this is true if M > C n ln(n), for some large C=C(r). Some listeners may have heard me talk a while back on the asymptotically precise statement: the same behavior holds for any fixed C> 1/r. Here I'll try to say something about the definitive ``hitting time" version.