Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/32847
Tipo: | Tese |
Título: | Conexões entre mecânica estatística e o lema local de Lovász: novas provas, novas cotas |
Autor(es): | Paula Mendes Soares Fialho |
Primeiro Orientador: | Aldo Procacci |
Segundo Orientador: | Bernardo Nunes Borges de Lima |
Primeiro membro da banca : | Albens Atman Picardi Faria |
Segundo membro da banca: | Daniel Ungaretiti Borges |
Terceiro membro da banca: | Gabriel de Morais Coutinho |
Quarto membro da banca: | Paulo Cupertino de Lima |
Quinto membro da banca: | Roberto Fernandéz |
Resumo: | Neste trabalho abordamos dois assuntos que inicialmente parecem não relacionados, mas que, como foi provado recentemente, apresentam uma importante interseção entre si: a convergência de gás de polímeros, em Mecânica Estatística, e o Lema Local de Lovász, em Combinatória. O gás de polímeros abstratos é um modelo discreto utilizado no estudo de diversos sistemas físicos. Um problema crucial para o modelo é encontrar um raio R tal que a pressão seja analítica e limitada no polidisco de raio R. A melhor cota para tal R é dada pelo critério de Fernández-Procacci, cuja prova envolve maquinário combinatorial pesado. Neste trabalho apresentamos uma nova prova alternativa para esse critério baseada em um simples argumento indutivo inspirado pela conexão entre o modelo de polímeros abstratos e o Lema Local de Lovász. O Lema Local de Lovász é uma importante ferramenta utilizada para provar a existência de determinados objetos em Combinatória, sendo frequentemente empregado em problemas envolvendo colorações de grafos. Nesse contexto, apresentamos um algoritmo inspirado no Lema Local de Lovász que fornece uma nova cota superior para o índice cromático acíclico de um grafo. Finalizamos este trabalho apresentando uma generalização desse algoritmo que também é aplicável nos demais problemas abordados pelo Lema Local de Lovász. |
Abstract: | 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. |
Assunto: | Matemática - Teses Mecânica estatística - Teses. Teoria dos grafos - Teses Algoritmos – Teses |
Idioma: | por |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE MATEMÁTICA |
Curso: | Programa de Pós-Graduação em Matemática |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/32847 |
Data do documento: | 14-Fev-2020 |
Aparece nas coleções: | Teses de Doutorado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Tese Paula Fialho.pdf | 1.01 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.