Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor
Transactions of the American Mathematical Society · 16.06.2023 · 376 (9) · 6623-6662
DOI: 10.1090/tran/8954 ↗Kurz gefasst
Fachartikel in der Zeitschrift Transactions of the American Mathematical Society, online erschienen am 16.06.2023. Verfasst von Dong Yeap Kang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: European Research Council, H2020 European Research Council, Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
We prove that for n ∈ N n \in \mathbb N and an absolute constant C C , if p ≥ C log 2 n / n p \geq C\log ^2 n / n and L i , j ⊆ [ n ] L_{i,j} \subseteq [n] is a random subset of [ n ] [n] where each k ∈ [ n ] k\in [n] is included in L i , j L_{i,j} independently with probability p p for each i , j ∈ [ n ] i, j\in [n] , then asymptotically almost surely there is an order- n n Latin square in which the entry in the i i th row and j j th column lies in L i , j L_{i,j} . The problem of determining the threshold probability for the existence of an order- n n Latin square was raised independently by Johansson [ Triangle factors in random graphs , 2006], by Luria and Simkin [Random Structures Algorithms 55 (2019), pp. 926–949], and by Casselgren and Häggkvist [Graphs Combin. 32 (2016), pp. 533–542]; our result provides an upper bound which is tight up to a factor of log n \log n and strengthens the bound recently obtained by Sah, Sawhney, and Simkin [ Threshold for Steiner triple systems , arXiv: 2204.03964 , 2022]. We also prove analogous results for Steiner triple systems and 1 1 -factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a 1 1 -factorization of a nearly complete regular bipartite graph.
Förderung
- European Research Council
- H2020 European Research Council
- Engineering and Physical Sciences Research Council
Zitieren
APA
Kang, D. Y., Kelly, T., Kühn, D., Methuku, A., & Osthus, D. (2023). Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor. Transactions of the American Mathematical Society, 376(9), 6623-6662. https://doi.org/10.1090/tran/8954
Vancouver
Kang DY, Kelly T, Kühn D, Methuku A, Osthus D. Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor. Transactions of the American Mathematical Society. 2023;376(9):6623-6662. doi:10.1090/tran/8954
BibTeX
@article{Kang2023,
author = {Kang, Dong Yeap and Kelly, Tom and Kühn, Daniela and Methuku, Abhishek and Osthus, Deryk},
title = {Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor},
journal = {Transactions of the American Mathematical Society},
year = {2023},
volume = {376},
number = {9},
pages = {6623--6662},
doi = {10.1090/tran/8954}
}
EUVIMED