Conexões entre mecânica estatística e o lema local de Lovász: novas provas, novas cotas

• Ano de defesa: 2020
• Autor(a) principal: Paula Mendes Soares Fialho
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE MATEMÁTICA; Programa de Pós-Graduação em Matemática; UFMG
• Palavras-chave em Português: Lema local de Lovász; Algoritmo de Moser-Tardos; Critério de Fernández-Procacci; Coloração acíclica de arestas; Matemática - Teses; Mecânica estatística - Teses.; Teoria dos grafos - Teses; Algoritmos – Teses
• Link de acesso: http://hdl.handle.net/1843/32847

In this text we study two subjects that initially seem unrelated but, as it was recently shown, there is an important connection between them: the abstract polymer gas in Statistical Mechanics and the Lovász Local Lemma in Combinatorics. The abstract polymer gas is a discrete model used to study a large number of physical systems. A key problem for the model is to ?nd radii R such that the pressure is analytic and bounded in the polydisc of radii R. The best bound for the radii was given by Fernández-Procacci criterion, whose proof involves heavy combinatorial machinery. In this text we provide an alternative proof of this criterion based on a simple inductive argument inspired by the connection between the abstract polymer model and the Lovász Local Lemma. The Lovász Local Lemma, which is an important tool used to prove the existence of some objects in Combinatorics, is commonly applied in problems concerning graph colorings. In this context, we provide an algorithm inspired by this lemma which allows us to obtain a new bound for the acyclic edge chromatic number. We conclude this text by presenting a generalization of this algorithm that can also be applied to other problems addressed by the Lovász Local Lemma.