Un punto de encuentro de probabilidad, grafos y algoritmos: la Lema Local de Lovász y resultados relacionados, una encuesta
Autores: Faragó, András
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Un punto de encuentro de probabilidad, grafos y algoritmos: la Lema Local de Lovász y resultados relacionados, una encuesta
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Lemma local de Lovász
Método probabilístico
Combinatoria
Eventos débilmente dependientes
Teoremas determinísticos
Aplicaciones
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 47
Citaciones: Sin citaciones
Un resultado clásico y fundamental, conocido como la Lema Local de Lovász, es una joya en el método probabilístico de combinatoria. A un alto nivel, su mensaje principal puede describirse por la afirmación de que eventos débilmente dependientes se comportan de manera similar a los independientes. Una característica fascinante de este resultado es que, aunque es una declaración puramente probabilística, proporciona una herramienta valiosa y versátil para probar teoremas completamente determinísticos. La Lema Local de Lovász ha encontrado muchas aplicaciones; a pesar de haber sido publicada originalmente en 1973, todavía atrae investigación novedosa y activa. En este artículo de revisión, repasamos varias formas de la Lema, así como algunos resultados y aplicaciones relacionadas.
Descripción
Un resultado clásico y fundamental, conocido como la Lema Local de Lovász, es una joya en el método probabilístico de combinatoria. A un alto nivel, su mensaje principal puede describirse por la afirmación de que eventos débilmente dependientes se comportan de manera similar a los independientes. Una característica fascinante de este resultado es que, aunque es una declaración puramente probabilística, proporciona una herramienta valiosa y versátil para probar teoremas completamente determinísticos. La Lema Local de Lovász ha encontrado muchas aplicaciones; a pesar de haber sido publicada originalmente en 1973, todavía atrae investigación novedosa y activa. En este artículo de revisión, repasamos varias formas de la Lema, así como algunos resultados y aplicaciones relacionadas.