Lovasz Local Lemma and (graphical) enumeration
by
Laszlo A. Szekely
University of South Carolina
Coauthors: Lincoln Lu

The Lovász Local Lemma is known to have an extension for cases where independence is missing but negative dependencies are under control. We show that this is often the case for random injections, and we provide easy-to-check conditions for the non-trivial task of verifying a negative dependency graph for random injections. As an application, we prove existence results for hypergraph packing and Turán type extremal problems. A more surprising application is that tight asymptotic lower bounds can be obtained for asymptotic enumeration problems using the Lovász Local Lemma. This is joint work with Lincoln Lu.

Date received: April 18, 2008