Alternative proofs of the asymmetric Lovász local lemma and Shearer’s lemma Ioannis Giotis Department of Mathematics, National and Kapodistrian University of Athens igiotis@cs.upc.edu Lefteris Kirousis Department of Mathematics, National and Kapodistrian University of Athens lkirousis@math.uoa.gr John Livieratos Department of Mathematics, National and Kapodistrian University of Athens jlivier89@math.uoa.gr Kostas I. Psaromiligkos Department of Mathematics, University of Chicago kostaspsa@math.uchicago.edu Dimitrios M. Thilikos Department of Mathematics, National and Kapodistrian University of Athens and AlGCo project, CNRS, LIRMM, France sedthilk@thilikos.info Abstract We provide new algorithmic proofs for two forms of the Lovász Local Lemma: the Asymmetric version and Shearer’s Lemma. Our proofs directly compute an upper bound for the probability that the corresponding Moser-type algorithms last for at least n steps. These algorithms iteratively sample the probability space; when and if they halt, a correct sampling, i.e. one where all undesirable events are avoided, is obtained. Our computation shows that this probability is exponentially small in n. In contrast most extant proofs for the Lovász Local Lemma and its variants use counting arguments that give estimates of only the expectation that the algorithm lasts for at least n steps. For the asymmetric version, we use the results of Bender and Richmond on the multivariable Lagrange inversion. For Shearer’s Lemma, we follow the work of Kolipaka and Szegedy, combined with Gelfand’s formula for the spectral radius of a matrix. 1 Introduction Suppose we have a number of “undesirable” events, defined on a common probability space, that we want to avoid. There are various sufficient conditions that guarantee that we can. One of the most useful and celebrated Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Editor, B. Coeditor (eds.): Proceedings of the XYZ Workshop, Location, Country, DD-MMM-YYYY, published at http://ceur-ws.org 148 such conditions, is the Lovász Local Lemma (LLL), which first appeared in a paper by Erdős and Lovász [EL75] in 1975. The sufficient conditions of LLL and its variants require that the probabilities of the undesirable events be upper bounded in terms of parameters of a graph that expresses the dependencies between the events (for a survey, see [Sze13]). The proofs of the original results were non-algorithmic Essentially, the first algorithmic proof of a special case of the symmetric LLL, where the sufficient condition requires a uniform bound for the probabilities of all events in terms of the number of dependencies of each event, was given by Moser [Mos09]. The first algorithmic proof of the asymmetric version, where the condition requires the existence of a number in (0, 1) for each event, such that the probability of each event to occur is bounded by an expression of these numbers, was given by Moser and Tardos [MT10]. These algorithmic results were expressed in the variable framework, where each event is assumed to depend on a number of independent random variables. The algorithms iteratively sample the variables; when and if they stop, a sampling where all undesirable events are avoided is obtained. Such algorithms were shown to come to a halt using a counting argument that became known as the “entropic method” [Tao09]. In this paper, we first prove the asymmetric LLL by directly computing an upper bound for the probability that the Moser-type algorithms last for at least n steps. This probability is expressed by a recurrence relation, which we solve by employing the result of Bender and Richmond on the multivariable Lagrange inversion formula [BR98]. Recurrence solving was also utilized for the symmetric LLL by Giotis et al. in [GKPT15]. Previous proofs in the literature that were based on counting arguments gave an estimate of only the expectation of the algorithm lasting for at least n steps. Furthermore, we give an algorithmic proof of the most general form of LLL, that of Shearer’s Lemma [She85]. This result gives a sufficient and necessary condition for avoiding all the undesirable events. Following closely the work of Kolipaka and Szegedy [KRS11], we again express the running time of a probabilistic algorithm by a recurrence relation, that we solve using Gelfand’s formula for the spectral radius of a matrix (see [HJ90]). The variable setting framework: Let Xi , i = 1, ..., l be mutually independent random variables on a common probability space, taking values in the finite sets Di , i = 1, ..., l respectively. Suppose also that E1 , . . . , Em are “undesirable” events. The scope sc(Ej ) of an event Ej is the minimal subset of variables such that one can determine whether Ej occurs or not knowing only their values. Events are assumed to be ordered according to their index. Our aim is to find an assignment of values such that none of the events occur. A dependency graph is now defined as follows: its vertex set is {1, ..., m}; two vertices i, j are connected with an edge if sc(Ei ) ∩ sc(Ej ) 6= ∅. We denote the neighborhood, in the dependency graph, of an event Ej by Nj (by assumption j ∈ / Nj ). We also assume that Nj 6= ∅, j = 1, . . . , m. This is a natural assumption, since it can be easily verified that “isolated” events can be ignored. 2 Asymmetric Lovász Local Lemma Our first objective is to provide an algorithmic proof of the following theorem: Theorem 2.1 (Asymmetric Lovász Local Lemma). Suppose that there exist χ1 , χ2 , . . . , χm ∈ (0, 1), such that Y Pr(Ej ) ≤ χj (1 − χi ), i∈Nj for all j ∈ {1, . . . , m}. Then, Pr[E 1 ∧ E 2 ∧ · · · ∧ E m ] > 0. To proceed with the proof of Theorem 2.1, consider M-Algorithm below. It successively produces random assignments, by resampling the variables in the scopes of occurring events, until it finds one under which no undesirable event occurs. When the variables in the scope of an occurring event Ej are resampled, the algorithm checks if Ej still occurs (lines 2 and 3 of the Resample routine) and, in case it doesn’t, proceeds to check its neighborhood. A round is the duration of any Resample call during an execution of M-Algorithm. A Resample call made from line 3 of the main algorithm is a root call, while one made from within another call is a recursive call. Lemma 2.2. Consider an arbitrary call of Resample(Ej ). Let Xj be the set of events that do not occur at the start of this call. Then, if and when this call terminates, all events in Xj ∪ {Ej } do not occur. 149 Algorithm 1 M-Algorithm. 1: Sample the variables Xi , i = 1, ..., l and let α be the resulting assignment. 2: while there exists an event that occurs under the current assignment, let Ej be the least indexed such event and do 3: Resample(Ej ) 4: end while 5: Output current assignment α. Resample(Ej ) 1: Resample the variables in sc(Ej ). 2: if Ej occurs then 3: Resample(Ej ) 4: else 5: while some event whose index is in Nj occurs under the current assignment, let Ek be the least indexed such event and do 6: Resample(Ek ) 7: end while 8: end if Proof. For the purposes of this proof, say that Resample(Ej ) is the main call, suppose it terminates and that α is the produced assignment of values. Furthermore, suppose that Ek ∈ Xj ∪ {Ej } and that Ek occurs under α. Let Ek ∈ Xj . Then, under the assignment at the beginning of the main call, Ek did not occur. Thus, it must be the case that at some point during this call, a resampling of some variables caused Ek to occur. Let Resample(Es ) be the last time Ek became occurring, and thus remained occurring until the end of the main call. During Resample(Es ), only the variables in sc(Es ) were resampled. Thus, Ek is in the neighborhood of Es . But then, by line 5 of the Resample routine, Resample(Es ) couldn’t have terminated and thus, neither could the main call. Contradiction. Thus Ek = Ej . Since under the assignment at the beginning of the main call, Ej occurred, by lines 2 and 3 of the Resample routine, it must be the case that during some resampling of the variables in sc(Ej ), Ej became non-occurring. The main call could not have ended after this resampling, since Ej occurs under the assignment α produced at the end of this call. Then, there exists some r ∈ Nj such that Resample(Er ) is the subsequent Resample call. Thus Ej ∈ Xr and we obtain a contradiction as in the case where Ek ∈ Xj above. An immediate corollary of Lemma 2.2, is that the events of the root calls of Resample are pairwise distinct, therefore there can be at most m such root calls in any execution of M-Algorithm. Consider now rooted forests, i.e. forests of trees such that each tree has a special node designated as its root, whose vertices are labeled by events Ej , j ∈ {1, . . . , m}. We will use such forests to depict the executions of M-Algorithm. Definition 2.3. A labeled rooted forest F is called feasible if: 1. the labels of its roots are pairwise distinct, 2. the labels of any two siblings (i.e. vertices with a common parent) are distinct and 3. an internal vertex labeled by Ej has either one child labeled again by Ej or at most |Nj | children, with labels whose indices are in Nj . The number of nodes of a feasible forest F is denoted by |F|. The nodes of such a labeled forest are ordered as follows: children of the same node are ordered as their labels are; nodes in the same tree are ordered by preorder (respecting the ordering between siblings) and finally if the label on the root of a tree T1 precedes the label of the root of T2 , all nodes of T1 precede all nodes of T2 . Given an execution of M-Algorithm that lasts for at least n rounds, we construct, in a unique way, a feasible forest with n nodes, by creating one node for each Resample call and labeling it with its argument, where the root calls correspond to the roots of the trees and a recursive call made from line 3 or 6 of a Resample(Ej ) call gives rise to a child of the corresponding node of this Resample(Ej ) call. We say that a feasible forest F 150 constructed this way is the n-witness forest of M-Algorithm’s execution and we define WF to be the event M-Algorithm executes with n-witness forest F. Define Pn to be the probability that M-Algorithm lasts for at least n rounds. It is easy to see that: " # [ X h i Pn = Pr WF = Pr WF , (1) F :|F |=n F :|F |=n where the last equality holds because the events WF are disjoint. It is easy to see that M-Algorithm introduces various dependencies to the probabilistic calculations. For example, suppose that the i-th node of a witness forest F is labeled by Ej and its children have labels with indices in Nj . Then, under the assignment produced at the end of the i-th round of this execution, Ej does not occur. To avoid such dependencies, we introduce ValAlg below. Algorithm 2 ValAlg. Input: Feasible forest F with labels Ej1 , . . . , Ejn . 1: Sample the variables Xi , i = 1, ..., l. 2: for s=1,. . . ,n do 3: if Ejs does not occur under the current assignment then 4: return failure and exit. 5: else 6: Resample the variables in sc(Ejs ) 7: end if 8: end for 9: return success. A round of ValAlg is the duration of any for loop executed at lines 2-8. If it manages to go through its input without coming upon a non-occurring event at any given round, it returns success.Thus, the success or failure of ValAlg is not conditioned on whether it produces an assignment such that no event occurs. The following result concerns the distribution of the random assignments at any round of ValAlg. Lemma 2.4 (Randomness Lemma). At the beginning of any given round of ValAlg, the distribution of the current assignment of values to the variables Xi , i = 1, ..., l, given that ValAlg has not failed, is as if all variables have been sampled anew. Proof. This follows from the fact that at each round, the variables for which their values have been exposed, are immediately resampled. Now, given a feasible forest F with n nodes, we say that F is validated by ValAlg if the latter returns success on input F. The event of this happening is denoted by VF . We also set: X P̂n = Pr[VF ]. (2) F : |F |=n Lemma 2.5. For any feasible forest F, the event WF implies the event VF , therefore Pn ≤ P̂n . Proof. Indeed, if the random choices made by an execution of M-Algorithm that produces as witness forest F are made by ValAlg on input F , then clearly ValAlg will return success. By Lemma 2.5, it suffices to prove that P̂n is exponentially small to n. For notational convenience, suppose that the neighborhood of an event Ej is Nj := {j1 , . . . , jkj }, j = 1, . . . , m P2m (recall that Nj is a set of indices of events). Now, let n = (n1 , . . . , n2m ), n1 , . . . , n2m ≥ 0 be such that i=1 ni = n and n − (1)j := (n1 , . . . , nj − 1, . . . , n2m ). Define, for j = 1, . . . , m, the multivariate generating functions: X X Qj (t) = Qn,j tn and Rj (t) = Rn,j tn , (3) n:nj ≥1 n:nm+j ≥1 151 where t = (t1 , . . . , t2m ), tn := tn1 1 · · · tn2m 2m and:   Qn,j = Pr[Ej ] Qn−(1)j ,j + Rn−(1)j ,j , (4) X     Rn,j = Pr[Ej ] · Qn1 ,j1 + Rn1 ,j1 · · · Qnkj ,jk + Rnkj ,jk (5) j j n1 +···+nkj =n−(1)m+j and where Qn,j = 0 (resp. Rn,j = 0) when nj = 0 (resp. nm+j = 0) and there exists an i 6= j (resp. i 6= m + j) such that ni ≥ 1 and Q0,j = R0,j = 1, where 0 is a sequence of 2m zeroes. Since a rooted tree is trivially a rooted forest, Definition 2.3 applies accordingly. Also, VT is the event the validation algorithm succeeds on input the feasible tree T . Now, consider the coefficients of the generating functions in (3). It is not difficult to see that, if T1 , T2 are two P2m feasible trees with n = i=1 ni nodes each, whose roots are labeled with Ej and where, T1 ’s root has a unique child labeled by Ej , whereas T2 ’s root has children labeled by indices in Nj , then: P r[VT1 ] ≤ Qn,j and P r[VT2 ] ≤ Rn,j . Also, observe that: X X     P̂n ≤ Qn1 ,1 + Rn1 ,1 · · · Qnm ,m + Rnm ,m . n n1 +...+nm =n Our aim is to show that both Qn,j and Rn,j are exponentially small to n, for any given sequence of n. Thus, by ignoring polynomial factors, the same will hold for P̂n . As an intuitive point for n = (n1 , . . . , n2m ), note that, in a feasible tree T , nj corresponds to the numbers of nodes u of T that have a unique child so that both u and its child are labeled with Ej, j = {1, . . . , 2m}. On the other hand, nm+j corresponds to the number of nodes labeled by Ej whose children are labeled by indices in Nj , j = 1, . . . , m. By multiplying both sides of (4) and (5) by tn and adding all over suitable n, we get the system of equations (Q, R): Qj (t) =tj fj ((Q, R)), Rj (t) =tm+j fm+j ((Q, R)), (6) where, for x = (x1 , . . . , x2m ) and j = 1 . . . , m: ! Y fj (x) =χj (1 − χi ) (xj + xm+j + 2), (7) i∈Nj Y fm+j (x) =χj (1 − χi )(xi + xm+i + 2). (8) i∈Nj To solve the system, we will directly use the result of Bender and Richmond in [BR98] (Theorem 2). Let g := prs2m be the 2m-ary projection on the s-th coordinate and let B be the set of trees B = (V (B), E(B)) whose vertex set is {0, 1, . . . , 2m} and with edges directed towards 0. By [BR98], we get: 1 X n2m ∂(g, f1n1 , . . . , f2m ) [tn ]g((Q, R)(t)) = Q2m [xn−1 ] , (9) j=1 nj B∈B ∂B where the term for a tree B ∈ B is defined as: ( ! ) n−1 Y Y ∂ nr [x ] f (x) , (10) ∂xi r r∈V (B) (i,r)∈E(B) where r ∈ {0, . . . , 2m} and f0n0 := g. We consider a tree B ∈ B such that (10) is not equal to 0. Thus, (i, 0) 6= E(B), for all i 6= s. On the other hand, (s, 0) ∈ E(B), lest vertex 0 is isolated, and each vertex has out-degree exactly one, lest a cycle is formed 152 ∂pr 2m (x) or connectivity is broken. From vertex 0, we get ∂x s s = 1. Since we are are interested only in factors of (10) that are exponential in n, we can ignore the derivatives (except the one for vertex 0), as they introduce only polynomial (in n) factors to the product. Thus, we have that (10) is equal to the coefficient of xn−1 in: m ( ! !) nj nm+j Y Y Y nj nj nm+j nm+j χj (1 − χi ) (xj + xm+j + 2) χj (1 − χi ) (xi + xm+i + 2) . (11) j=1 i∈Nj i∈Nj We will say that the first part of (11) is the one with the factors whose exponents are nj and the second, those whose exponents are nm+j , j = 1, . . . , n. We now group the factors of each part of (11) separately, according to the i’s. We have already argued each vertex i has out-degree 1. Note also that the j’s such that i ∈ Nj are exactly P the j ∈ Ni . Thus, the exponent of the term xi + xm+i + 2 in the first part of (11) is ni and in the second, j∈Ni nm+j . Taking all this together, we get that the product of (11) is equal to: m ( ! !) P P P nm+i Y ni j∈Ni nj ni j∈Ni nm+j j∈Ni nm+j χi (1 − χi ) (xi + xm+i + 2) χi (1 − χi ) (xi + xm+i + 2) . (12) i=1 Using the binomial theorem and by ignoring polynomial factors, we get that the coefficient of xn−1 in (12) is: m  ! P ! Y ni P j∈Ni nj ni nm+i nm+i P j∈Ni nm+j −nm+i j∈Ni nm+j χi (1 − χi ) (1 − χi ) χi (1 − χi ) . (13) i=1 ni nm+i P j∈Ni nm+j By expanding (χi + 1 − χi ) , we get that (13) is at most: m ! ! m Y P Y P j∈Ni nj ni χi (1 − χi ) (1 − χi ) nm+i < (1 − χi ) j∈Ni nj (1 − χi )nm+i . (14) i=1 i=1 Q2m P2m By letting χ := mini=1,...,m {χi }, we obtain that (14) is bounded from above by i=1 (1 − χi ) = (1 − χi ) i=1 . Thus, [tn ]g((Q, R)(t̄)) ≤ (1 − χ)n , which is exponentially small to n. Thus, the proof is now complete. 3 Shearer’s Lemma We now turn our attention to Shearer’s Lemma. For a graph G with vertex set V := {1, . . . , m}, an independent set I is a subset of V with no edges between its vertices (∅ is trivially such a set). Let I(G) = {I0 , I1 , . . . , Is } denote the set of independent sets of G and suppose that its elements are ordered according to their indices, where I0 = ∅. For any I ∈ I(G), let N (I) be the set of vertices of I, together with their neighboring ones in G. Following [KRS11], we sat that I covers J if J ⊆ N (I). Theorem 3.1 (Shearer’s Lemma). Given a graph G = (V, E) on m vertices and a vector p̄ = (p1 , . . . , pm ) ∈ (0, 1)m , the following are equivalent: 1. For all I ∈ I(G), qI (G, p̄) = J∈I(G): I⊆J (−1)|J\I| j∈J pj > 0, P Q 2. For every (finite) sequence of events E1 , . . . , Em , if their dependency graph is G and if P r[Ej ] = pj , j = 1, . . . , m, then P r[E 1 ∧ · · · ∧ E m ] > 0. We will not be concerned with the proof of (2 ⇒ 1). It is the direction that gives us the necessity of condition 1 (see [She85]). The algorithm we will use is the Generalized Resample algorithm, designed by Kolipaka and Szegedy in[KRS11]. Abusing the notation, we will sometimes say that an independent set I ∈ I(G) contains events (instead of indices of events). Also, for any I = {j1 , ..., jk } ∈ I(G), k ≥ 0, let vbl(I) denote the set of variables contained in the scopes of the events in I. A round of GenResample is the duration of each repetition of lines 2 and 3. Let Pn be the probability GenResample executes for at least n rounds. Our aim again, is to show that there is a d ∈ (0, 1) such that Pn ≤ dn . Consider an execution of GenResample that lasts for at least n rounds and let Ii1 , . . . Iin be the independent sets selected at line 2. 153 Algorithm 3 GenResample. 1: Sample the variables Xi , i = 1, ..., l and let α be the resulting assignment. 2: while there exists an event that occurs under the current assignment, let Ii be the least indexed maximal independent set that contains only occurring events and do 3: Resample every variable in vbl(Ii ) and let α be the current assignment. 4: end while 5: Output current assignment α. Lemma 3.2. Iit covers Iit+1 , for all t ∈ {1, . . . , n − 1}. Proof. It suffices to prove that if the index of an event is in Iit+1 , then it is also in N (Iit ). Suppose Ej is in Iit+1 . Then, under the assignment produced at the end of round t, Ej occurred. To obtain a contradiction, suppose that Ej ∈ / N (Iit ). Ej does not occur at the beginning of round t, lest Iit is not maximal. But then, since it is not dependent on any event in Iit , it cannot occur at the beginning of round t + 1. Thus, Ej ∈ / Iit+1 . Contradiction. Now, as in the previous section, we will depict an execution of GenResample by a graph structure. In place of forests, we will now use directed paths, that have one vertex of in-degree 0 (source), one of out-degree 0 (sink), and all edges directed from the source to the sink. The vertices of such a path are labeled by independent sets from I(G) and we order them from the source to the sink. Definition 3.3. A directed labeled path P with |P| = n vertices, whose labels are Ii1 , . . . , Iin , is feasible if Iit covers Iit+1 , for all t ∈ {1, . . . , n} (in the terminology of [KRS11], (Ii1 , . . . , Iik ) is a stable set sequence). A feasible path with n nodes, whose labels correspond to the independent sets selected by GenResample in an execution that lasted for at least n rounds, is called the n-witness path of GenResample’s execution. Again, we want to avoid the dependencies that GenResample produces during its execution. We will thus use a validation algorithm, in the spirit of ValAlg of section 2. The rounds of GenVal are defined as usual. Algorithm 4 GenVal. Input: Feasible path P with labels Ii1 , . . . , Iin . 1: Sample the variables Xi , i = 1, ..., l. 2: for t=1,. . . ,n do 3: if there exists an event Ej , with j ∈ Iit , that does not occur under the current assignment then 4: return failure and exit. 5: else 6: Resample the variables in vbl(Iit ) 7: end if 8: end for 9: return success. Also, Lemma 2.4 holds for GenVal too. Define VP to be the event that GenVal returns success, on input P and suppose we have real numbers Qn,i suchQ that P r[VP ] ≤ Qn,i , where P is a path with n-nodes, whose source is labeled by Ii ∈ I(G) and where Q1,I = j∈I pj , for all I ∈ I(G). Thus, it holds that the numbers Qn,i satisfy: Y X Qn,i = pj Qn−1,J . (15) j∈Ii Ii covers J Following again the terminology of Q [KRS11], we define the stable set matrix M , as an s×s matrix, whose element in the i-th row and j-th column is j∈I pj if I covers J and 0 otherwise. Furthermore, let qn = (Qn,1 , . . . , Qn,s ). Easily, (15) is equivalent to: qn = M qn−1 , thus qn = M n−1 q1 . (16) Note now that: s X Pn ≤ Qn,i = kqn k1 , i=1 154 where k · k1 is the 1-norm defined on Rs . It is known that any vector norm, and thus 1-norm too, yields a norm for square matrices called the induced norm [HJ90] as follows: kM xk1 kM q1 k1 kM k1 := sup ≥ . (17) x6=0 kxk1 kq1 k1 By (16) and (17), we have that: kqn k1 = kM n−1 q1 k1 ≤ kM n−1 k1 · kq1 k1 . (18) Since kq1 k1 is a constant, it suffices to show that kM n−1 k1 is exponentially small in n. Let ρ(M ) be the spectral radius of M (see [KRS11]). By Gelfand’s formula (see again [HJ90]) used for the induced matrix norm k · k1 , we have that: ρ(M ) = lim kM n k1/n . n→∞ Furthermore, in [KRS11] (Theorem 14), it is proved that the condition of Shearer’s Lemma, i.e. Theorem 3.1 in our work, is equivalent to ρ(M ) < 1. Thus, by selecting an  > 0 such that ρ(M ) +  < 1, we have that there exists a constant (depending only on , M ) such that kM n−1 k1 ≤ (ρ(M ) + )n−1 , which, together with (18), gives us that the bound for Pn is exponentially small in n. Acknowledgements L. Kirousis’ research was partially supported by the Special Account for Research Grants of the National and Kapodistrian University of Athens. K. I. Psaromiligkos’ research was carried out while he was an undergraduate student at the Department of Mathematics of the National and Kapodistrian University of Athens. D. Thilikos’ research was supported by the project “ESIGMA” (ANR-17-CE40-0028). References [BR98] Edward A Bender and L Bruce Richmond. A multivariate Lagrange inversion formula for asymptotic calculations. The Electronic Journal of Combinatorics, 5(1):33, 1998. [EL75] Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets, 10:609-627, 1975. [GKPT15] Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, and Dimitrios M. Thilikos. On the al- gorithmic Lovász local lemma and acyclic edge coloring. In Proceedings of the twelfth workshop on analytic algorithmics and combinatorics. Society for Industrial and Applied Mathematics, 2015. http://epubs.siam.org/doi/pdf/10.1137/1.9781611973761.2. [HJ90] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge University Press, 1990. [KRS11] Kashyap Kolipaka, Babu Rao, and Mario Szegedy. Moser and Tardos meet Lovász. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 235-244. ACM, 2011. [Mos09] Robin A. Moser. A constructive proof of the Lovász local lemma. In Proceedings of the 41st annual ACM Symposium on Theory of Computing, pages 343-350, 2009. [MT10] Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. Journal of the ACM (JACM), 57(2):11, 2010. [She85] James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241-245, 1985. [Sze13] M. Szegedy. The Lovász local lemma - a survey. In Springer, editor, Computer Science - Theory and Applications, pages 11-23, 2013. [Tao09] Terence Tao. Moser’s entropy compression argument. 2009. Available: https://terrytao. wordpress.com/2009/08/05/mosers-entropy-compression-argument/. 155