Asymptotics for Shamir's Problem

DOI10.1016/J.AIM.2023.109019MaRDI QIDQ6325336arXivFDO

Authors J. Kahn

Publication date 15 September 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.AIM.2023.109019

Mathematics Subject Classification ID

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

arXiv classification

math.CO

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.

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)