Thresholds for edge colorings

02/22/2023 3:30 pm - 4:30 pm

Probability Seminar

Speaker: Vishesh Jain (University of Illinois Chicago)
Title: Thresholds for edge colorings
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 from [n], then with high probability, there is a proper edge coloring where the color of each edge comes from the corresponding list. We also prove analogous results for Latin squares and Steiner triple systems. This resolves several related conjectures of Johansson, Luria-Simkin, Casselgren-Häggkvist, Simkin, and Kang-Kelly-Kühn-Methuku-Osthus. I will discuss some of the main ingredients which go into the proof: the Kahn-Kalai conjecture, absorption, and the Lovasz Local Lemma distribution. Based on joint work with Huy Tuan Pham.