Abstract | The Lovász Local Lemma (LLL) is a powerful tool that can be used to prove that an object
having none of a set of bad properties exists, using the probabilistic method. In many applications
of the LLL it is also desirable to explicitly construct the combinatorial object. Recently it was
shown that this is possible using a randomized algorithm in the full asymmetric LLL setting [R.
Moser and G. Tardos, 2010]. A strengthening of the LLL for the case of dense local neighborhoods
proved in [R. Bissacot et al., 2010] was recently also made constructive in [W. Pegden, 2011]. In
another recent work [B. Haupler, B. Saha, A. Srinivasan, 2010], it was proved that the algorithm
of Moser and Tardos is still efficient even when the number of events is exponential. Here we
prove that these last two contributions can be combined to yield a new version of the LLL. |