• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2002.tde-05052013-214912
Documento
Autor
Nome completo
Élcio Lebensztayn
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2002
Orientador
Banca examinadora
Machado, Fabio Prates (Presidente)
Fontes, Luiz Renato Goncalves
Vachkovskaia, Marina
Título em português
O modelo de percolação em grafos: Um estudo de condições para a transição de fase do parâmetro crítico
Palavras-chave em português
Amenabilidade Forte
Constantes de Cheeger
Percolação em grafos
Transição de fase
Resumo em português
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.
Título em inglês
Percolation model on graphs: A study of conditions for phase transition
Palavras-chave em inglês
Cheeger constants
Percolation on graphs
Phase transition
Strong amenability
Resumo em inglês
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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Perte.pdf (644.72 Kbytes)
Data de Publicação
2013-05-13
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.