We provide new algorithmic proofs for two forms of the Lovasz 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 Lovasz 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.
Suppose we have a number of \undesirable" events, de ned on a common probability space, that we want to avoid. There are various su cient 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 such conditions, is the Lovasz Local Lemma (LLL), which rst appeared in a paper by Erd}os and Lovasz [EL75] in 1975. The su cient 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 rst algorithmic proof of a special case of the symmetric LLL, where the su cient 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 rst 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 rst 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 su cient 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]).
Let Xi, i = 1; :::; l be mutually independent random variables on a common probability space, taking values in the nite 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 nd an assignment of values such that none of the events occur.
A dependency graph is now de ned as follows: its vertex set is f1; :::; mg; 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 2= Nj ). We also assume that Nj 6= ;, j = 1; : : : ; m. This is a natural assumption, since it can be easily veri ed that \isolated" events can be ignored. 2
Theorem 2.1 (Asymmetric Lovasz Local Lemma). Suppose that there exist 1; 2; : : : ; m 2 (0; 1), such that Pr(Ej ) j
Y (1 i2Nj i); for all j 2 f1; : : : ; mg. Then, Pr[E1 ^ E2 ^
^ Em] > 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 nds 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 [ fEj g do not occur. Algorithm 1 M-Algorithm. 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 2 Xj [ fEj g and that Ek occurs under .
Let Ek 2 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 2 Nj such that Resample(Er) is the subsequent
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 2 f1; : : : ; mg. We will use such forests to depict the executions of M-Algorithm.
3. an internal vertex labeled by Ej has either one child labeled again by Ej or at most jNj j children, with labels whose indices are in Nj .
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 nally 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 constructed this way is the n-witness forest of M-Algorithm's execution and we de ne WF to be the event
De ne Pn to be the probability that M-Algorithm lasts for at least n rounds. It is easy to see that: Pn = Pr "
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
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.
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:
P^n =
X F: jFj=n
Pr[VF ]: 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
For notational convenience, suppose that the neighborhood of an event Ej is Nj := fj1; : : : ; jkj g, j = 1; : : : ; m (recall that Nj is a set of indices of events). Now, let n = (n1; : : : ; n2m), n1; : : : ; n2m 0 be such that Pi2=m1 ni = n and n (1)j := (n1; : : : ; nj 1; : : : ; n2m). De ne, for j = 1; : : : ; m, the multivariate generating functions:
X n:nj 1 Qj(t) =
Qn;jtn and Rj(t) =
X n:nm+j 1
Rn;jtn; (1) (2) (3) where t = (t1; : : : ; t2m), tn := t1n1
X 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 = f1; : : : ; 2mg. 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): (4) (5) (6) (7) (8) (9) (10) where, for x = (x1; : : : ; x2m) and j = 1 : : : ; m:
Qj (t) =tj fj ((Q; R));
Rj (t) =tm+j fm+j ((Q; R)); fj (x) = j fm+j (x) = j
Y (1 i2Nj Y (1 i2Nj
! i) (xj + xm+j + 2); i)(xi + xm+i + 2): 1 ( 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 f0; 1; : : : ; 2mg and with edges directed towards 0. By [BR98], we get: [tn]g((Q; R)(t)) =
Qj2=m1 nj B2B
X [xn 1] @(g; f1n1 ; : : : ; f2nm2m ) ;
@B [xn 1] Y
Y r2V (B) (i;r)2E(B)
) frnr (x) ; where the term for a tree B 2 B is de ned as: where r 2 f0; : : : ; 2mg and f0n0 := g.
We consider a tree B 2 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) 2 E(B), lest vertex 0 is isolated, and each vertex has out-degree exactly one, lest a cycle is formed or connectivity is broken. From vertex 0, we get @prs2m(x) = 1. Since we are are interested only in factors of (10) @xs 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 coe cient of xn 1 in: m ( Y j=1 nj Y (1 j i2Nj
! i)nj (xj + xm+j + 2)nj nm+j Y (1 j i)nm+j (xi + xm+i + 2)nm+j !) : (11) We will say that the rst 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 2 Nj are exactly the j 2 Ni. Thus, the exponent of the term xi + xm+i + 2 in the rst part of (11) is ni and in the second, Pj2Ni nm+j . Taking all this together, we get that the product of (11) is equal to:
! ini (1 i)Pj2Ni nj (xi + xm+i + 2)ni inm+i (1 i)Pj2Ni nm+j (xi + xm+i + 2)Pj2Ni nm+j !) : (12) (13) (14) Using the binomial theorem and by ignoring polynomial factors, we get that the coe cient of xn 1 in (12) is: By expanding ( i + 1
i)Pj2Ni nm+j , we get that (13) is at most: ini (1 i)Pj2Ni nj i)nm+i inm+i (1 i)Pj2Ni nm+j nm+i
Pj2Ni nm+j nm+i ! : m ( Y i=1 m Y i=1 m Y i=1 ni ni ! (1
! ini (1 i)Pj2Ni nj (1 i)nm+i i)Pj2Ni nj (1
i)nm+i : !
m < Y(1 i=1 By letting := mini=1;:::;mf ig, we obtain that (14) is bounded from above by Qi2=m1(1 i) = (1 Thus, [tn]g((Q; R)(t)) (1 )n, which is exponentially small to n. Thus, the proof is now complete. i)Pi2=m1 . 3
We now turn our attention to Shearer's Lemma. For a graph G with vertex set V := f1; : : : ; mg, an independent set I is a subset of V with no edges between its vertices (; is trivially such a set). Let I(G) = fI0; I1; : : : ; Isg denote the set of independent sets of G and suppose that its elements are ordered according to their indices, where I0 = ;. For any I 2 I(G), let N (I) be the set of vertices of I, together with their neighboring ones in G.
Theorem 3.1 (Shearer's Lemma). Given a graph G = (V; E) on m vertices and a vector p = (p1; : : : ; pm) 2 (0; 1)m, the following are equivalent: 1. For all I 2 I(G), qI (G; p) = PJ2I(G): I J ( 1)jJnIj Qj2J pj > 0, 2. For every ( nite) sequence of events E1; : : : ; Em, if their dependency graph is G and if P r[Ej ] = pj , j = 1; : : : ; m, then P r[E1 ^ ^ Em] > 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 2 I(G) contains events (instead of indices of events). Also, for any I = fj1; :::; jkg 2 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 2 (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. 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
Lemma 3.2. Iit covers Iit+1 , for all t 2 f1; : : : ; n
1g.
Proof. It su ces 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 2= 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 2= Iit+1 .
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.
De nition 3.3. A directed labeled path P with jPj = n vertices, whose labels are Ii1 ; : : : ; Iin , is feasible if Iit covers Iit+1 , for all t 2 f1; : : : ; ng (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 de ned as usual. Algorithm 4 GenVal.
4: 5: 6: Resample the variables in vbl(Iit ) 7: end if 8: end for 9: return success.
Input: Feasible path P with labels Ii1 ; : : : ; Iin . 1: Sample the variables Xi, i = 1; :::; l. 2: for t=1,. . . ,n do
assignment then
return failure and exit.
else Also, Lemma 2.4 holds for GenVal too. De ne VP to be the event that GenVal returns success, on input P and suppose we have real numbers Qn;i such that P r[VP ] Qn;i, where P is a path with n-nodes, whose source is labeled by Ii 2 I(G) and where Q1;I = Qj2I pj , for all I 2 I(G).
Thus, it holds that the numbers Qn;i satisfy: Following again the terminology of [KRS11], we de ne the stable set matrix M , as an s s matrix, whose element in the i-th row and j-th column is Qj2I pj if I covers J and 0 otherwise. Furthermore, let qn = (Qn;1; : : : ; Qn;s).
Qn;i =
Y pj j2Ii
X Ii covers J
Qn 1;J : qn = M qn 1; thus qn = M n 1q1:
Pn
s X Qn;i = kqnk1; i=1 where k k1 is the 1-norm de ned 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 k1 := sup kM xk1 x6=0 kxk1 kM q1k1 : Since kq1k1 is a constant, it su ces to show that kM n 1k1 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 nk1=n:
n!1 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 1k1 ( (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). (17) (18) [BR98]
calculations. The Electronic Journal of Combinatorics, 5(1):33, 1998.
Paul Erd}os and Laszlo Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions. In nite and Finite Sets, 10:609-627, 1975. [HJ90] [KRS11]
of the forty-third annual ACM symposium on Theory of computing, pages 235-244. ACM, 2011.
ACM Symposium on Theory of Computing, pages 343-350, 2009.