Asymptotics for Shamir's Problem

For fixed $r\ge 3$ and $n$ divisible by $r$, let ${\mathcal H}={\mathcal H}^r_{n,M}$betherandom$M$-edge$r$-graphon$V={1,\ldots ,n}$;thatis,${\mathcal H}$ischosenuniformlyfromthe$M$-subsetsof${\mathcal K}:={V \choose r}$($:= {\mbox{$r$-subsets of $V$}}$). Shamir’s Problem (circa 1980) asks, roughly, for what $M=M(n)$ is $\mathcal{H}$ likely to contain a perfect matching (that is, $n\mathrm{/}r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. The present paper has two purposes. First, it establishes the asymptotically correct version of the 2008 result: Theorem 1. For fixed $ϵ>0$ and $M>(1+ϵ)(n\mathrm{/}r)\log n$, $P(\mathcal{H}containsaperfectmatching)\to 1$ as $n\to \mathrm{\infty }$. Second, it begins a proof of the definitive ``hitting time" statement: Theorem 2. If $A_1,\dots$ is a uniform permutation of $\mathcal{K}$, ${\mathcal{H}}_t=\{A_1,\dots ,A_t\}$, and $T=\min{t:A_1\cup \cdots\cup A_t=V},$then$P({\mathcal H}_T ~\mbox{contains a perfect matching})\rightarrow 1 $as$n\rightarrow\infty$. It is shown here that Theorem 2 follows from a conditional version of Theorem 1 that will be proved elsewhere. The key ideas in that proof are similar to those for Theorem 1, but the argument is a longer story, and it has seemed best to give the present separate proof of Theorem 1, in which those ideas may appear more clearly.