Loading...
Please wait, while we are loading the content...
Similar Documents
A constructive proof of the general Lovász Local Lemma (2009)
| Content Provider | CiteSeerX |
|---|---|
| Author | Tardos, Gábor Moser, Robin A. |
| Abstract | The Lovász Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08]. In [Mos09], a constructive proof was presented that works under negligible restrictions, formulated in terms of the Bounded Occurrence Satisfiability problem. In the present paper, we reformulate and improve upon these findings so as to directly apply to almost all known applications of the general Local Lemma. |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Powerful Tool Restrictive Condition Breakthrough Paper Bec91 General Lov Sz Local Lemma Several Publication Bounded Occurrence Satisfiability Problem General Local Lemma Local Lemma El75 Negligible Restriction Local Lemma Constructive Variant Prescribed Collection Constructive Proof Combinatorial Object |
| Content Type | Text |
