Talk:Lovász local lemma

From Wikipedia, the free encyclopedia

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)

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