Threshold for Steiner triple systems
Abstract We prove that with high probability $$\mathbb {G}^{(3)}(n,n^{-1+o(1)})$$ G...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151139 |
| _version_ | 1824457975167713280 |
|---|---|
| author | Sah, Ashwin Sawhney, Mehtaab Simkin, Michael |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Sah, Ashwin Sawhney, Mehtaab Simkin, Michael |
| author_sort | Sah, Ashwin |
| collection | MIT |
| description | Abstract
We prove that with high probability
$$\mathbb {G}^{(3)}(n,n^{-1+o(1)})$$
G
(
3
)
(
n
,
n
-
1
+
o
(
1
)
)
contains a spanning Steiner triple system for
$$n\equiv 1,3\pmod {6}$$
n
≡
1
,
3
(
mod
6
)
, 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. |
| first_indexed | 2024-09-23T09:56:53Z |
| format | Article |
| id | mit-1721.1/151139 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:18:32Z |
| publishDate | 2023 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1511392024-12-23T05:19:36Z Threshold for Steiner triple systems Sah, Ashwin Sawhney, Mehtaab Simkin, Michael Massachusetts Institute of Technology. Department of Mathematics Abstract We prove that with high probability $$\mathbb {G}^{(3)}(n,n^{-1+o(1)})$$ G ( 3 ) ( n , n - 1 + o ( 1 ) ) contains a spanning Steiner triple system for $$n\equiv 1,3\pmod {6}$$ n ≡ 1 , 3 ( mod 6 ) , 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. 2023-07-20T17:49:52Z 2023-07-20T17:49:52Z 2023-06-19 2023-07-19T03:23:11Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151139 Sah, Ashwin, Sawhney, Mehtaab and Simkin, Michael. 2023. "Threshold for Steiner triple systems." en https://doi.org/10.1007/s00039-023-00639-6 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer Nature Switzerland AG application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Sah, Ashwin Sawhney, Mehtaab Simkin, Michael Threshold for Steiner triple systems |
| title | Threshold for Steiner triple systems |
| title_full | Threshold for Steiner triple systems |
| title_fullStr | Threshold for Steiner triple systems |
| title_full_unstemmed | Threshold for Steiner triple systems |
| title_short | Threshold for Steiner triple systems |
| title_sort | threshold for steiner triple systems |
| url | https://hdl.handle.net/1721.1/151139 |
| work_keys_str_mv | AT sahashwin thresholdforsteinertriplesystems AT sawhneymehtaab thresholdforsteinertriplesystems AT simkinmichael thresholdforsteinertriplesystems |