Hitting times for Shamir's problem

DOI10.1090/TRAN/8508MaRDI QIDQ5020682zbMATH OpenOpenAlexFDO

Authors J. Kahn

Publication date 7 January 2022

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.01605

zbMATH Keywords

thresholdhitting timeperfect matchingrandom hypergraphShamir's problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Combinatorial probability (60C05) Hypergraphs (05C65) Stopping times; optimal stopping problems; gambling theory (60G40)

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$. More recently the author proved the asymptotically correct version of that result: for fixed $C>1/r$ and $M>Cnlogn$, $$n ightarrowinfty$$ The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: $mboxTheorem.$ If $A_1,ldots$ is a uniform permutation of $mathcalK$, ${mathcalH}_t=A_{1}dots{A}_t$, and [ T=min{t:A_1cup cdotscup A_t=V}, ] then $$n ightarrowinfty$$.

Recommendations

• Asymptotics for Shamir's problem
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Factors in random graphs
• scientific article; zbMATH DE number 949656
• Perfect matchings in random s‐uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• A BK inequality for randomly drawn subsets of fixed size
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A tail bound for read-\(k\) families of functions
• A threshold for perfect matchings in random d-pure hypergraphs
• Are many small sets explicitly small?
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Factors in random graphs
• Improved bounds for the sunflower lemma
• Inequalities with applications to percolation and reliability
• Introduction to Random Graphs
• Lopsided Lovász Local lemma and Latin transversals
• On the combinatorial problems which I would most like to see solved
• On the cycle space of a random graph
• On the existence of a factor of degree one of a connected random graph
• Percolation
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Perfect matchings in random s‐uniform hypergraphs
• Perfect matchings in random uniform hypergraphs
• The Small Giant Component in Scale-Free Random Graphs
• The chromatic number of dense random graphs
• The probabilistic method
• Threshold functions
• Thresholds and Expectation Thresholds
• Thresholds versus fractional expectation-thresholds

Cited in

(8)

• Multitrees in random graphs
• The hitting time of clique factors
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Threshold for Steiner triple systems
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• A robust Corrádi-Hajnal theorem
• Searching for (sharp) thresholds in random structures: where are we now?
• Asymptotics for Shamir's problem

This page was built for publication: Hitting times for Shamir's problem

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