The Entropy Compression Method

Graduate Student Colloquium
Friday, October 7, 2022 - 3:30pm for 1 hour (actually 50 minutes)
Skiles 005
Abhishek Dhawan – Georgia Tech Math – adhawan7@gatech.edu
Abhishek Dhawan

The Lovasz Local Lemma is a powerful tool to prove existence of combinatorial structures satisfying certain properties. In a constructive proof of the LLL, Moser and Tardos introduced a proof technique that is now referred to as the entropy compression method. In this talk I will describe the main idea of the method and apply it to a problem easily solved using the LLL. I will also describe recent applications of the idea to various graph coloring problems.