Talk:Lovász local lemma

[Untitled]

Where did the figure of 8 come from in the example? It seems to me that each pair depends on at most 4n-2 others. (If so, 6 and 10 would be possible values for d - corresponding to n=2 and n=3 respectively - but 8 would not.) Is there something I'm missing? Nitish 20:48, 13 January 2006 (UTC)[reply]

I think actually each pair depends on at most 4k-2 others, where k is the number of colors, and I've editted the article to reflect this.

I originally picked this example when I wrote the article as the simplest one I could think of, but even here the dependence issue is a bit tricky (as I showed by messing it up in the original article). Is there any simpler example that also avoids large amounts of calculation?

One other thing that probably would be worth expanding on is the claim that the lemma is nonconstructive. There have been some recent 'algorithmic' versions of the lemma which can be used to sometimes give constructive proofs of results obtained by the lemma. However, I'm not familiar enough with those versions to write about them at the moment. Kevinatilusa

I think it is worth it to specify clearly the independence assumption that is required. For example, A_i independent of {A_j}_{j\in S_i} (of the whole generated sigma-algebra of these events, not pairwise), where k-|S_i|-1<=d. Although the required notion could be much weaker. — Preceding unsigned comment added by 128.100.3.6 (talk) 20:48, 26 February 2012 (UTC)[reply]

Symmetric bound

Currently we say that Lemma III implies $epd\leq 1$ suffices. However it actually implies the even stronger that $ep(d-1/2)\leq 1$ suffices, at least for $d>1$ . Would it make sense to update with this bound? 188.120.84.157 (talk) 19:51, 20 October 2015 (UTC)[reply]