{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:36:54Z","timestamp":1760236614426,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T00:00:00Z","timestamp":1638921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A classic and fundamental result, known as the Lov\u00e1sz Local Lemma, is a gem in the probabilistic method of combinatorics. At a high level, its core message can be described by the claim that weakly dependent events behave similarly to independent ones. A fascinating feature of this result is that even though it is a purely probabilistic statement, it provides a valuable and versatile tool for proving completely deterministic theorems. The Lov\u00e1sz Local Lemma has found many applications; despite being originally published in 1973, it still attracts active novel research. In this survey paper, we review various forms of the Lemma, as well as some related results and applications.<\/jats:p>","DOI":"10.3390\/a14120355","type":"journal-article","created":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T21:52:32Z","timestamp":1639086752000},"page":"355","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Meeting Point of Probability, Graphs, and Algorithms: The Lov\u00e1sz Local Lemma and Related Results\u2014A Survey"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8952-6946","authenticated-orcid":false,"given":"Andr\u00e1s","family":"Farag\u00f3","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, 800 W. Campbell Rd., Richardson, TX 75080, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,8]]},"reference":[{"key":"ref_1","unstructured":"Alon, N., and Spencer, J.H. (2016). The Probabilistic Method, Wiley. [4th ed.]."},{"key":"ref_2","first-page":"609","article-title":"Problems and Results on 3-chromatic Hypergraphs and Some Related Questions","volume":"Volume 2","author":"Hajnal","year":"1973","journal-title":"Infinite and Finite Sets"},{"key":"ref_3","first-page":"1108","article-title":"A Random Walk in and Around Mathematics\u2014Interview with L\u00e1szl\u00f3 Lov\u00e1sz","volume":"182","author":"Laczkovich","year":"2021","journal-title":"Magyar Tudom\u00e1ny (Hung. Sci.)"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02579368","article-title":"On a Problem of Spencer","volume":"5","author":"Shearer","year":"1985","journal-title":"Combinatorica"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","article-title":"Asymptotic Lower Bounds for Ramsey Functions","volume":"20","author":"Spencer","year":"1997","journal-title":"Discret. Math."},{"key":"ref_6","unstructured":"Harvey, N.J.A., and Vondr\u00e1k, J. (2017). Short Proofs for Generalizations of the Lov\u00e1sz Local Lemma: Shearer\u2019s Condition and Cluster Expansion. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/BF01195001","article-title":"Coloring a Graph Frugally","volume":"17","author":"Hind","year":"1997","journal-title":"Combinatorica"},{"key":"ref_8","unstructured":"Sinclair, A. (2021, December 01). CS271 Randomness & Computation: Spring 2020, Lecture 22. Available online: https:\/\/people.eecs.berkeley.edu\/~sinclair\/cs271\/s20.html."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s004930050061","article-title":"Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules","volume":"19","author":"Leighton","year":"1999","journal-title":"Combinatorica"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/rsa.3240020402","article-title":"An Algorithmic Approach to the Lov\u00e1sz Local Lemma","volume":"2","author":"Beck","year":"1991","journal-title":"Random Struct. Algorithms"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1667053.1667060","article-title":"A Constructive Proof of the General Lov\u00e1sz Local Lemma","volume":"57","author":"Moser","year":"2010","journal-title":"J. ACM"},{"key":"ref_12","unstructured":"Szegedy, M. (2013, January 25\u201329). The Lov\u00e1sz Local Lemma\u2014A Survey. Proceedings of the 8th International Computer Science Symposium in Russia (CSR 2013), Ekaterinburg, Russia."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1023\/A:1006350622830","article-title":"Local Search Algorithms for SAT: An Empirical Evaluation","volume":"24","author":"Hoos","year":"2000","journal-title":"J. Autom. Reason."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2132","DOI":"10.1137\/100799642","article-title":"Deterministic Algorithms for the Lov\u00e1sz Local Lemma","volume":"42","author":"Chandrasekaran","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_15","unstructured":"Jain, V., Pham, H.T., and Vuong, T.D. (2020). Towards the Sampling Lov\u00e1sz Local Lemma. arXiv."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3268930","article-title":"Approximate Counting, the Lov\u00e1sz Local Lemma, and Inference in Graphical Models","volume":"66","author":"Moitra","year":"2019","journal-title":"J. ACM"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Kempe, J., and Sattath, O. (2010, January 6\u20138). A Quantum Lov\u00e1sz Local Lemma. Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC\u201910), Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806712"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"He, K., Li, Q., Sun, X., and Zhang, J. (2019, January 23\u201326). Quantum Lov\u00e1sz Local Lemma: Shearer\u2019s Bound is Tight. Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC\u201919), Phoenix, AZ, USA.","DOI":"10.1145\/3313276.3316392"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3365004","article-title":"Distributed Edge Coloring and a Special Case of the Constructive Lov\u00e1sz Local Lemma","volume":"16","author":"Chang","year":"2020","journal-title":"ACM Trans. Algorithms"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.aim.2019.06.031","article-title":"Measurable Versions of the Lov\u00e1sz Local Lemma and Measurable Graph Colorings","volume":"353","author":"Bernshteyn","year":"2019","journal-title":"Adv. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/355\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:42:57Z","timestamp":1760168577000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,8]]},"references-count":20,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120355"],"URL":"https:\/\/doi.org\/10.3390\/a14120355","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,8]]}}}