Using Lovász Local Lemma in the Space of Random Injections

Abstract

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.