IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Checking Hats with the Lopsided Lovasz Local Lemma

  • Oct. 9, 2020
  • 2:30 p.m.


The famous Hatcheck Problem imagines $n$ individuals checking their hats at a restaurant and each receiving a randomly chosen hat after dinner. What is the probability that nobody receives their own hat? We will explore a new proof that this probability tends to $\frac{1}{e}$ with $n$. The proof makes use of the lopsided Lovasz local lemma and is striking for two reasons. First, there is a precise sense in which the original local lemma is wholly unsuited for the task, yet the seemingly mild generalization found in the lopsided version allows it to fully circumvent this difficulty. Second, the probabilistic content of the proof is readily transformed into a simple injection argument. The proof therefore demonstrates how one may wield a more powerful version of the local lemma through elementary means.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster