Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/EABA-9E5HRZ
Type: | Tese de Doutorado |
Title: | Duas aplicações da mecânica estatística: percolação em grafos infinitos e lema local de Lovász algorítmico |
Authors: | Rogerio Gomes Alves |
First Advisor: | Aldo Procacci |
First Co-advisor: | Remy de Paiva Sanchis |
First Referee: | Bernardo Nunes Borges de Lima |
Second Referee: | Ronald Dickman |
Third Referee: | Roberto Imbuzeiro Felinto de Oliveira |
metadata.dc.contributor.referee4: | Rodrigo Bissacot Proença |
Abstract: | 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. |
Subject: | Matemática Percolação Mecanica estatistica |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/EABA-9E5HRZ |
Issue Date: | 3-Dec-2013 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tese048.pdf | 685.92 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.