Lema local de Lovász
Lovász local lemma
- Fecha
- 1975 · fiabilidad baja
- Lugar
- Budapest, Hungría
- Autoría
- Paul Erdős y László Lovász (1975)
- Ámbito
- Saber y símbolos
Qué se descubrió
Resultado de teoría de la probabilidad que relaja la condición de independencia total entre sucesos, garantizando una probabilidad positiva de que ninguno ocurra si son 'casi' independientes; herramienta clave del método probabilístico.
A qué dio paso
- desarrollo del método probabilístico en combinatoria
- algoritmos de coloración de grafos
- versión algorítmica constructiva del lema (Moser-Tardos)
- aplicaciones en teoría de Ramsey