Este trabalho visa a estudar o modelo de percolação independente, de Bernoulli, em grafos, tendo como objetivo principal obter condições que garantam a ocorrência de transição de fase. Iniciamos apresentando as definições e algumas técnicas fundamentais para o modelo de percolação (de elos ou de sítios) em um grafo infinito, conectado e localmente finito. Demonstramos então dois resultados essenciais: os fatos do parâmetro crítico não depender da escolha do vértice e da existência de um aglomerado infinito ter probabilidade 0 ou 1. Também obtemos um limitante inferior para o parâmetro crítico quando o grafo é de grau limitado. Para finalizar esta parte introdutória, analisamos a percolação em grafos particulares, a saber, a rede hipercúbica Z^d (para a qual mostramos a existência de transição de fase em dimensão d >= 2 e a unicidade do aglomerado infinito na fase supercrítica) e alguns tipos de árvores (para as quais apresentamos os parâmetros críticos). Na parte mais importante da dissertação, tendo como base os trabalhos de Benjamini e Schramm, de Häggström, Schonmann e Steif e de Lyons e Peres, introduzimos os conceitos de transitividade, amenabilidade e amenabilidade forte para um grafo. Fazemos uma detalhada discussão destas definições: provamos que a constante de Cheeger ancorada não depende do vértice em que é ancorada, estudamos relações entre os conceitos (amenabilidade e amenabilidade forte são noções distintas, bem como condições necessárias e suficientes para ambas) e calculamos a constante de Cheeger e a constante de Cheeger ancorada para alguns grafos. Finalmente, utilizando a técnica de crescimento do aglomerado, apresentamos para a probabilidade crítica um limitante superior que depende da constante ancorada. Isto nos permite concluir que ocorre transição de fase para qualquer grafo infinito, conectado, fracamente não-amenável (de constante de Cheeger ancorada positiva) e de grau limitado. / This work intends to study independent Bernoulli percolation model on graphs; the main purpose is obtaining conditions for phase transition. We begin presenting the definitions and some basic techniques for bond percolation and site percolation models on infinite, connected, locally finite graphs. We prove two essential results: the critical parameter is independent of the choice of the vertex and the probability that there exists an infinite cluster takes the values 0 and 1 only. We also obtain a lower bound for critical parameter when the graph is of bounded degree. To finish this preliminary part, we analyze percolation on particular graphs, namely the d-dimensional cubic lattice Z^d (for which we prove that there exists phase transition in dimension d >= 2 and the uniqueness of the infinite cluster in supercritical phase) and some trees (for which we present the critical parameters). In the most important part of this essay, founded in the works of Benjamini and Schramm, Häggström, Schonmann and Steif and Lyons and Peres, we introduce the concepts of transitivity, amenability and strong amenability. We discuss in detail these definitions: we prove that anchored Cheeger constant does not depend on the choice of the vertex, we study some relations (amenability and strong amenability are distinct notions, and necessary and sufficient conditions for both) and we obtain Cheeger constant and anchored Cheeger constant for some graphs. Finally, using the growing cluster technique, we present for the critical probability an upper bound that depends on the anchored constant. This permits us to conclude that there exists phase transition on infinite, connected, weakly non-amenable graphs of bounded degree.
Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-05052013-214912 |
Date | 15 January 2002 |
Creators | Lebensztayn, Élcio |
Contributors | Machado, Fabio Prates |
Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
Source Sets | Universidade de São Paulo |
Language | Portuguese |
Detected Language | Portuguese |
Type | Dissertação de Mestrado |
Format | application/pdf |
Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0018 seconds