• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2002.tde-05052013-214912
Document
Auteur
Nom complet
Élcio Lebensztayn
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2002
Directeur
Jury
Machado, Fabio Prates (Président)
Fontes, Luiz Renato Goncalves
Vachkovskaia, Marina
Titre en portugais
O modelo de percolação em grafos: Um estudo de condições para a transição de fase do parâmetro crítico
Mots-clés en portugais
Amenabilidade Forte
Constantes de Cheeger
Percolação em grafos
Transição de fase
Resumé en portugais
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.
Titre en anglais
Percolation model on graphs: A study of conditions for phase transition
Mots-clés en anglais
Cheeger constants
Percolation on graphs
Phase transition
Strong amenability
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Perte.pdf (644.72 Kbytes)
Date de Publication
2013-05-13
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.