• 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
 
 
Disertación de Maestría
DOI
10.11606/D.45.2002.tde-05052013-214912
Documento
Autor
Nombre completo
Élcio Lebensztayn
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2002
Director
Tribunal
Machado, Fabio Prates (Presidente)
Fontes, Luiz Renato Goncalves
Vachkovskaia, Marina
Título en 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
Palabras clave en portugués
Amenabilidade Forte
Constantes de Cheeger
Percolação em grafos
Transição de fase
Resumen en 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 en inglés
Percolation model on graphs: A study of conditions for phase transition
Palabras clave en inglés
Cheeger constants
Percolation on graphs
Phase transition
Strong amenability
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Perte.pdf (644.72 Kbytes)
Fecha de Publicación
2013-05-13
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.