Hitting times for Shamir's problem

DOI10.1090/TRAN/8508zbMATH Open1479.05326arXiv2008.01605OpenAlexW3127579929MaRDI QIDQ5020682FDOQ5020682

Authors: J. Kahn 

Publication date: 7 January 2022

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

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$$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Percolation
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On the combinatorial problems which I would most like to see solved
• The probabilistic method
• Factors in random graphs
• Title not available (Why is that?)
• Perfect matchings in random uniform hypergraphs
• Perfect matchings in random s‐uniform hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Threshold functions
• Thresholds and Expectation Thresholds
• Title not available (Why is that?)
• On the existence of a factor of degree one of a connected random graph
• Introduction to Random Graphs
• Title not available (Why is that?)
• Are many small sets explicitly small?
• A BK inequality for randomly drawn subsets of fixed size
• Inequalities with applications to percolation and reliability
• Lopsided Lovász Local lemma and Latin transversals
• The chromatic number of dense random graphs
• A tail bound for read-\(k\) families of functions
• The Small Giant Component in Scale-Free Random Graphs
• On the cycle space of a random graph
• A threshold for perfect matchings in random d-pure hypergraphs
• Improved bounds for the sunflower lemma
• 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
• A robust Corrádi-Hajnal theorem
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• 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)