## Quest for Negative Dependency Graphs

- March 12, 2012
- 3:50 p.m.
- LeConte 312

## Abstract

In order to apply the lopsided version of the LovĂˇsz Local Lemma, the events of interest must form a negative dependency graph, which is easier to satisfy (but harder to identify) than the dependency graph required by the original version. We will explore settings regarding four disparate combinatorial objects in which proper negative dependency graphs exist (or are conjectured to exist): perfect matchings, partitions, spanning trees, and permanents of doubly-stochastic matrices. (No previous exposure to the Local Lemma is assumed, so feel free to attend even if you missed the first talk.)