Threshold for Steiner triple systems

DOI10.1007/S00039-023-00639-6zbMATH Open1518.05021arXiv2204.03964OpenAlexW4381164947MaRDI QIDQ6173554FDOQ6173554

Michael Simkin, Mehtaab Sawhney, Ashwin Sah

Publication date: 21 July 2023

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Abstract: We prove that with high probability $mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $nequiv1,3pmod6$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park.

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

Recommendations

• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Large girth approximate Steiner triple systems
• scientific article
• Almost all Steiner triple systems have perfect matchings
• An upper bound on the number of Steiner triple systems

zbMATH Keywords

thresholdsrandom assignment problemexpectation thresholds

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05) Triple systems (05B07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Spanning trees in random graphs
• On a packing and covering problem
• Counting designs
• The probabilistic method
• Factors in random graphs
• Title not available (Why is that?)
• Edge-decompositions of graphs with high minimum degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Avoiding Arrays of Odd Order by Latin Squares
• Hamiltonian circuits in random graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Thresholds and Expectation Thresholds
• On Pósa's Conjecture for Random Graphs
• On the existence of a factor of degree one of a connected random graph
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Edge-disjoint Hamilton cycles in random graphs
• Are many small sets explicitly small?
• Hunting for sharp thresholds
• Large deviations in random latin squares
• The Turán problem for projective geometries
• Robust Hamiltonicity of Dirac graphs
• A threshold for perfect matchings in random d-pure hypergraphs
• Asymptotic packing via a branching process
• Fractional Clique Decompositions of Dense Partite Graphs
• Two-Sided, Unbiased Version of Hall’s Marriage Theorem
• Thresholds versus fractional expectation-thresholds
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Improved bounds for the sunflower lemma
• Pseudorandom hypergraph matchings
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Minimalist designs
• Hitting times for Shamir’s problem
• Asymptotics for Shamir's problem
• On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs
• The threshold for the square of a Hamilton cycle
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Threshold for Steiner triple systems

Cited In (4)

• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Substructures in Latin squares
• Threshold for Steiner triple systems
• Searching for (sharp) thresholds in random structures: where are we now?

This page was built for publication: Threshold for Steiner triple systems

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