Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

2022/12/12 by Vishesh Jain, Jain, Vishesh, Huy Tuan Pham +1 · 3 citations
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2212.06109

openalex publication_date 2022/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the threshold for the binomial random 3-partite, 3-uniform hypergraph G³((n,n,n),p) to contain a Latin square is Θ(logn/n). We also prove analogous results for Steiner triple systems and proper list edge-colorings of the complete (bipartite) graph with random lists. Our results answer several related questions of Johansson, Luria-Simkin, Casselgren-Häggkvist, Simkin, and Kang-Kelly-Kühn-Methuku-Osthus.

Cited by

• On fractional triangle decompositions of random graphs
• Refined Absorption: A New Proof of the Existence Conjecture and its Applications to Extremal and Probabilistic Design Theory
• No-(k+1)-in-line problem for large constant k

Related

• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• The optimal edge-colouring threshold
• Threshold for Steiner triple systems
• Thresholds for (n,q,2)-Steiner Systems via Refined Absorption
• Note on random Latin squares and the triangle removal process