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

Detalhes bibliográficos
Ano de defesa: 2020
Autor(a) principal: Paula Mendes Soares Fialho
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
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
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/32847
Resumo: 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.