Inicio  /  Algorithms  /  Vol: 14 Par: 12 (2021)  /  Artículo
ARTÍCULO
TITULO

A Meeting Point of Probability, Graphs, and Algorithms: The Lovász Local Lemma and Related Results?A Survey

András Faragó    

Resumen

A classic and fundamental result, known as the Lovász 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ász 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.

 Artículos similares

       
 
Taimur Ali Shams, Syed Irtiza Ali Shah, Muhammad Ayaz Ahmad, Kashif Mehmood, Waseem Ahmad and Syed Tauqeer ul Islam Rizvi    
Landing gear system of an aircraft enables it to take off and land with safety and comfort. Because of the horizontal and vertical velocity of aircraft, upon landing, the complete aircraft undergoes different forcing functions in the form of the impact f... ver más
Revista: Applied Sciences

 
Craig W. Siders, Thomas Galvin, Alvin Erlandson, Andrew Bayramian, Brendan Reagan, Emily Sistrunk, Thomas Spinka and Constantin Haefner    
Scaling the particle beam luminosity from laser wakefield accelerators to meet the needs of the physics community requires a significant, thousand-fold increase in the average power of the driving lasers. Multipulse extraction is a promising technique ca... ver más
Revista: Instruments

 
Adebayo Omotosho,Truman Tyoden,Peace Ayegba,Joyce Ayoola     Pág. pp. 94 - 109
The importance of students? involvement in classroom and non-classroom university courses cannot be overemphasized in the process of learning. But, students for several reasons must be motivated to enhance their continuous participation, especially in no... ver más

 
A. Galieva,O. Nevzorova     Pág. 85 - 93
This paper discusses main sources and methodology of compiling the Tatar-Russian Socio-Political Dictionary of collocations. The area of collocations within the language system is of particular importance, and the well-known language-specificity of collo... ver más

 
Rachael McKee, Björn Elsäßer and Pál Schmitt    
The quantification of the reflection of water waves is of paramount importance in coastal and marine engineering. Reflected waves are produced as a result of an incident wave meeting a reflective boundary e.g., in a wave basin. While reflection can be se... ver más