Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.1999.tde-20210729-023709
Document
Auteur
Nom complet
Alexandre Scalzitti
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 1999
Directeur
Titre en portugais
Convergência na teoria de grafos aleatórios
Mots-clés en portugais
Teoria Dos Grafos
Resumé en portugais
O objeto de estudo desta dissertação é o modelo 'G IND.n,p(n)' de grafos aleatórios. Estudamos a probabilidade de 'G IND.n,p(n)' satisfazer propriedades que podem ser expressas numa teoria de primeira ordem de grafos. O estudo desta probabilidadeé feito em termos assintóticos, ou seja, quando o número de vértices n de 'G IND.n,p(n)' tende ao infinito. Particularmente, estamos interessados no caso em que a probabilidade acima mencionada converge para 0 ou para 1 (lei zero-um). Como ferramenta no estudo dessa probabilidade, utilizamos o Jogo de Ehrenfeucht. Apresentamos dois importantes resultados na área: o de Glebskii-Fagin e de Shelah-Spencer
Titre en anglais
not available
Resumé en anglais
The object of study in this dissertation is the model 'G IND.n,p(n)' for random graphs. We study the probability of 'G IND.n,p(n)' satisfying graph properties which can be expressed in a first-order theory. The study of this probability is donein asymptotic terms, that is, when the number of vertices n of 'G IND.n,p(n)' tends to infinity. In particular, we are interested in the case that this probability converges to 0 or 1 (zero-one laws). As a tool in the study of this probability,we use the Ehrenfeucht Game and Theorem. We present two major results in the field: the Glebskii-Fagin Theorem as well as the Shelah-Spencer Theorem
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.
Date de Publication
2021-07-29
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.