For fixed $r\geq 3$ and $n$ divisible by $r$, let ${ \mathcal H}={ \mathcal H}^r_{ n,M}$ be the random $M$-edge $r$-graph on $V=\{ 1,\ldots ,n\}$; that is, ${ \mathcal H}$ is chosen uniformly from the $M$-subsets of ${ \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/r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\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({ \mathcal H} ~\mbox{ contains a perfect matching})\rightarrow 1 \,\,\, \mbox{ as $n\rightarrow\infty$}.$ The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: $\mbox{ Theorem.}$ If $A_1, \ldots ~$ 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 \,\,\, \mbox{ as $n\rightarrow\infty$}$.
Categories: math.CO