Conexões entre mecânica estatística e o lema local de Lovász: novas provas, novas cotas
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Albens Atman Picardi Faria
Daniel Ungaretiti Borges
Gabriel de Morais Coutinho
Paulo Cupertino de Lima
Roberto Fernandéz
Daniel Ungaretiti Borges
Gabriel de Morais Coutinho
Paulo Cupertino de Lima
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
Palavras-chave
Lema local de Lovász, Algoritmo de Moser-Tardos, Critério de Fernández-Procacci, Coloração acíclica de arestas