the lopsided Local Lemma
/ LOH-vahs /
The lopsided Local Lemma is a strengthening of the Lovasz Local Lemma that replaces strict mutual independence by a one-sided correlation condition, dramatically widening its applicability — especially to permutations and matchings where genuine independence never holds. In the ordinary LLL one needs each bad event to be mutually independent of the events outside its neighbourhood. But in many natural settings the bad events are positively dependent on each other (knowing one bad event occurred makes the others slightly more likely too), and crucially conditioning on avoiding some bad events only makes the remaining one less likely, not more. The lopsided version sees that this favourable, one-sided dependence is all the LLL proof actually uses.
Define a lopsidependency graph: B_i is joined to B_j only when B_i and B_j are positively correlated in the strong sense required. The defining requirement is the lopsided condition: for every bad event B_i and every collection of other bad events indexed by the non-neighbours, the conditional probability satisfies P(B_i given that all those non-neighbour events are avoided) <= P(B_i). In words, avoiding the events it does not depend on never increases the chance of B_i. Under this weaker hypothesis — together with the same arithmetic criterion ep(d+1) <= 1 or the asymmetric x_i system, but now d counting only lopsidependency neighbours — the same conclusion holds: P(no bad event occurs) > 0. Because lopsidependency graphs can be far sparser than ordinary dependency graphs, the criterion is satisfied in many more cases.
Its key arena is structures with a uniform random permutation or random perfect matching, where any two constraints overlap and so are never independent, yet are negatively associated in exactly the lopsided sense. This is how one proves, for instance, existence of Latin transversals (a permutation avoiding repeated symbols in a coloured matrix when no colour appears too often), and it underlies the lopsided form's use in additive combinatorics and pattern-avoidance. The honest caveat is that verifying the lopsidependency condition is a real analytic task: it is not enough that events 'mostly do not interact'; you must establish the precise inequality P(B_i given avoidance of non-neighbours) <= P(B_i), typically via a negative-association or coupling argument, and getting the dependency graph wrong invalidates the whole conclusion.
Latin transversal: in an n-by-n matrix where every symbol appears at most (n-1)/(4e) times, there is a permutation sigma so that the entries (i, sigma(i)) are all distinct. Pick sigma uniformly at random; bad event B_{ijk...} = 'two cells with the same symbol both lie on the chosen diagonal'. These events are never independent (sigma is one global object), but conditioning on avoiding the others only lowers each one's probability — the lopsided condition holds — and the criterion is met, so a Latin transversal exists.
Lopsided LLL: needs only P(B_i | avoid non-neighbours) <= P(B_i), so it works for permutations and matchings.
The one-sided condition must be proved, not assumed: you need P(B_i | avoidance of its non-neighbours) <= P(B_i) exactly, usually via negative association or a coupling; a wrong lopsidependency graph voids the conclusion.