Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/32847
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Aldo Procacci | pt_BR |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/1401825985537837 | pt_BR |
dc.contributor.advisor2 | Bernardo Nunes Borges de Lima | pt_BR |
dc.contributor.advisor2Lattes | http://lattes.cnpq.br/6614000692805715 | pt_BR |
dc.contributor.referee1 | Albens Atman Picardi Faria | pt_BR |
dc.contributor.referee2 | Daniel Ungaretiti Borges | pt_BR |
dc.contributor.referee3 | Gabriel de Morais Coutinho | pt_BR |
dc.contributor.referee4 | Paulo Cupertino de Lima | pt_BR |
dc.contributor.referee5 | Roberto Fernandéz | pt_BR |
dc.creator | Paula Mendes Soares Fialho | pt_BR |
dc.creator.Lattes | http://lattes.cnpq.br/5211033518748774 | pt_BR |
dc.date.accessioned | 2020-03-11T19:28:38Z | - |
dc.date.available | 2020-03-11T19:28:38Z | - |
dc.date.issued | 2020-02-14 | - |
dc.identifier.uri | http://hdl.handle.net/1843/32847 | - |
dc.description.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. | pt_BR |
dc.description.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. | pt_BR |
dc.description.sponsorship | CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | ICX - DEPARTAMENTO DE MATEMÁTICA | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Matemática | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Lema local de Lovász | pt_BR |
dc.subject | Algoritmo de Moser-Tardos | pt_BR |
dc.subject | Critério de Fernández-Procacci | pt_BR |
dc.subject | Coloração acíclica de arestas | pt_BR |
dc.subject.other | Matemática - Teses | pt_BR |
dc.subject.other | Mecânica estatística - Teses. | pt_BR |
dc.subject.other | Teoria dos grafos - Teses | pt_BR |
dc.subject.other | Algoritmos – Teses | pt_BR |
dc.title | Conexões entre mecânica estatística e o lema local de Lovász: novas provas, novas cotas | pt_BR |
dc.type | Tese | pt_BR |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Tese Paula Fialho.pdf | 1.01 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.