IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.)

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