Duas aplicações da mecânica estatística: percolação em grafos infinitos e lema local de Lovász algorítmico
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
Bernardo Nunes Borges de Lima
Ronald Dickman
Roberto Imbuzeiro Felinto de Oliveira
Rodrigo Bissacot Proença
Ronald Dickman
Roberto Imbuzeiro Felinto de Oliveira
Rodrigo Bissacot Proença
Resumo
Nesta tese mostramos um critério geral para que grafos infinitos de grau limitado tenham uma transição de fase não trivial para o processo de Percolação de elos independentes baseado em uma única desigualdade isoperimétrica, se o grafo possui geodésicas bi-infinitas, ou duas desigualdades isoperimétricas, caso não as tenha. Mostramosque nos grafos desta classe, sem geodésicas bi-infinitas, a conectividade finita decai subexponencialmente na região altamente supercrítica, mesmo se p está arbitrariamente próximo de 1. Os grafos naquela classe, com geodésicas bi-infinitas, sempre tem a função de conectividade finita decaindo exponencialmente se p está próximo de1 o suficiente. Estudamos também o Lema Local de Lovász construtivo de Moser e Tardos [59] e mostramos que há uma relação entre o algoritmo proposto por estes autores e a expansão em polímeros do gás de rede ao identificarmos a noção de witness trees noalgoritmo com a noção de árvores de Penrose da expansão. Essa relação nos permite concluir que o algoritmo de Moser-Tardos é eficiente se a expansão em polímeros é convergente.
Abstract
In this work we show a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a biinfinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesicalways have finite connectivity functions with exponential decay when p is suffciently close 1. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays subexponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close 1. We also point out a close connection between the Moser-Tardos algorithmic version of the Lovász local lemma [59] and the cluster expansion of the hard-core lattice gas in statistical mechanics. We show that the notion of witness trees given by Moser andTardos is essentially coincident with that of Penrose trees in the Cluster expansion scheme of the hard-core gas. Such an identification implies that the Moser-Tardos algorithm is successful in a polynomial time if the cluster expansion converges.
Assunto
Matemática, Percolação, Mecanica estatistica
Palavras-chave
Função conectividade, Lema Local de Lovász algorítmico, Percolação, Transição de fase, Expansão em polímeros