New bounds for the Moser-Tardos distribution

The Lovasz local lemma (LLL) is a probabilistic tool to generate combinatorial structures with good local properties. The LLL-distribution further shows that these structures have good global properties in expectation. The seminal algorithm of Moser and Tardos turned the simplest, variable-based form of the LLL into an efficient algorithm; this has since been extended to other probability spaces including random permutations. One can similarly define an MT-distribution for these algorithms, that is, the distribution of the configuration they produce. We show new bounds on the MT-distribution in the variable and permutation settings which are significantly stronger than those known to hold for the LLL-distribution. As some example illustrations, we show a nearly tight bound on the minimum implicate size of a CNF Boolean formula, and we obtain improved bounds on weighted Latin transversals and partial Latin transversals.