EUVIMEDEUVIMED entdecken
Crossref

Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →