IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Diamonds in the Rough (The Lovász Local Lemma)

  • Feb. 27, 2012
  • 3:50 p.m.
  • LeConte 312

Abstract

The Lovász Local Lemma is a well-known probabilistic technique commonly used to prove the existence of rare combinatorial objects. The lopsided (or negative dependency graph) version of the lemma is more powerful but appears infrequently in literature due to the lack of settings in which the additional generality has thus far been needed. We will begin with the original lemma of Lovász and build up to the most general lopsided version. As a case study, we will examine a rich collection of events in the space of random perfect matchings that defines a proper negative dependency graph.

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