MIT-Harvard-MSR Combinatorics Seminar

Speaker:  Huy Tuan Pham  (Standord University)

Title:  Thresholds for Latin squares and Steiner triple systems

Abstract:   

We show that if each edge of the complete bipartite graph K_n,n is given a random list of C(\log _n) colors among n colors, then with high probability, there is a proper edge coloring where the color of each edge comes from the corresponding list. In other words, a random 3-partite 3-uniform hypergraph with parts of size n and edge density C(\log _n)/n contains a Latin square with high probability. This resolves a conjecture of Luria and Simkin on threshold for containment of a Latin square, and the related conjecture of Simkin on threshold for containment of a Steiner triple system. Based on joint work with Vishesh Jain.