CMSA Probability Seminar: Thresholds for edge colorings

SEMINARS, CMSA EVENTS

Speaker:

Vishesh Jain - University of Illinois Chicago

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.

This seminar will be held on Zoom. For more information on how to join, please see: https://cmsa.fas.harvard.edu/event_category/probability-seminar/