HITTING TIMES FOR SHAMIR'S PROBLEM

For fixed r >= 3 and n divisible by r, let H = H-n,M(r) be the random M-edge r-graph on V = {1,..., n}; that is, H is chosen uniformly from the M-subsets of K := ((V)(r)) (:= {r-subsets of V}). Shamir's Problem (circa 1980) asks, roughly, for what M = M(n) is H likely to contain a perfect matching (that is, n/r disjoint r-sets)? In 2008 Johansson, Vu and the author showed that this is true for M > C(r)n log n. More recently the author proved the asymptotically correct version of that result: for fixed C > 1/r and M > Cn log n, P(H contains a perfect matching) -> 1 as n -> infinity. The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: Theorem. If A(1),... is a uniform permutation of K, H-t = {A(1),..., A(t)}, and T = min{t : A(1) boolean OR center dot center dot center dot boolean AND A(t) = V}, then P(H-T contains a perfect matching) -> 1 as n -> infinity.