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

Autor:	Jain, Vishesh, Pham, Huy Tuan
Rok vydání:	2022
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics Mathematics - Probability
Druh dokumentu:	Working Paper
Popis:	We show that the threshold for the binomial random $3$-partite, $3$-uniform hypergraph $G^{3}((n,n,n),p)$ to contain a Latin square is $\Theta(\log{n}/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\"aggkvist, Simkin, and Kang-Kelly-K\"uhn-Methuku-Osthus. Comment: 10 pages. Simplified proof; results unchanged
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2212.06109 Zobrazit plný text záznamu View this record from Arxiv