Uma versão algorítmica do Lema Local de Lovász

• Bruno Pasqualotto Cavalar

DOI: https://doi.org/10.5753/etc.2017.3189

Resumo

O Lema Local de Lovász (LLL) é uma ferramenta poderosa para provar a existência de objetos combinatórios que satisfazem um dado conjunto de restrições. Mais precisamente, dado uma coleção finita A de eventos “ruins”, o LLL dá condições suficientes para que a probabilidade P TA2A A seja positiva. Em um celebrado artigo [Moser and Tardos 2010], Moser e Tardos desenvolveram um algoritmo para encontrar eficientemente tais objetos cuja existência é garantida pelo LLL. Esse trabalho discute aplicações do LLL em problemas de combinatória e aplica o algoritmo de Moser e Tardos nesses problemas.