Asymptotics for Shamir's Problem

DOI10.1016/J.AIM.2023.109019arXiv1909.06834MaRDI QIDQ6325336FDOQ6325336

J. Kahn

Publication date: 15 September 2019

Abstract: For fixed $rgeq3$ and $n$ divisible by $r$, let $mathcalH={mathcalH}_{n,M}^r$ be the random $M$-edge $r$-graph on $V=1,ldots,n$; that is, $mathcalH$ is chosen uniformly from the $M$-subsets of $mathcalK:=Vchooser$ ($$r$-subsetsof$V$$). Shamir's Problem (circa 1980) asks, roughly, for what $M=M(n)$ is $mathcalH$ 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}nlogn$. The present paper has two purposes. First, it establishes the asymptotically correct version of the 2008 result: Theorem 1. For fixed $epsilon>0$ and $M>(1+epsilon)(n/r)logn$, $P(mathcalHmboxcontainsaperfectmatching)ightarrow1$ as $nightarrowinfty$. Second, it begins a proof of the definitive ``hitting time" statement: Theorem 2. If $A_1,ldots$ is a uniform permutation of $mathcalK$, ${mathcalH}_t=A_1,ldots,A_t$, and $T=mint:A_{1}cupcdotscup{A}_t=V,$ then $P({mathcalH}_{T}mboxcontainsaperfectmatching)ightarrow1$ as $nightarrowinfty$. 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.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

This page was built for publication: Asymptotics for Shamir's Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325336)