论文标题
打击Shamir问题的时间
Hitting times for Shamir's Problem
论文作者
论文摘要
对于固定的$ r \ geq 3 $和$ n $由$ r $划分的，让$ {\ Mathcal H} = {\ Mathcal H}^r_ {n，m} $是随机$ M $ -M $ -EDGE $ -EDGE $ R $ -GRAPH $ v = \ {1，\ ldots，n \ n \} $;也就是说，$ {\ Mathcal H} $是从$ {\ Mathcal k}的$ m $ -subsets均匀选择的：= {v \ select osece r} $（$：= \ {\ {\ mbox {$ r $ -sbox {$ r $ -subset of $ v $ v $} \} $）。 Shamir的问题（大约1980年）大致问，$ m = m（n）$是$ {\ mathcal h} $可能包含完美匹配（即，$ n/r $ diScoint $ r $ - $ -set）？ 在2008年的Johansson，VU和作者表明，对于$ m> c_rn \ log n $，这是正确的。最近，作者证明了该结果的渐近正确版本：对于固定的$ c> 1/r $和$ m> cn \ log n $，$ p（{\ Mathcal h}〜\ mbox {包含完美的匹配}）\ rightarrow 1 \，\，\，\，\，\，\ mbox {AS $ n \ n \ rirtar \ n \ $ 目前的工作完成了最新的“打击时间”陈述的证据，该证明是从最近的论文开始的： $ \ mbox {theorem。} $如果$ a_1，\ ldots〜 $是$ {\ Mathcal k} $的均匀置换，$ {\ Mathcal H} _t = \ {a_1 \ {a_1 \ dots a_t a_t a_t a_t a_t a _t a _t a _t \} a_t = v \}，\]然后$ p（{\ Mathcal H} _t〜 \ mbox {包含完美的匹配}）\ rightarrow 1 \，\，\，\，\ mbox {AS $ n \ rightArrow \ rightArrow \ rightArrow \ infty $} $。
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$}$.
