ETD system

Electronic theses and dissertations repository

 

Tesi etd-09192013-153720


Thesis type
Elaborati finali per laurea triennale
Author
PARENTE, FRANCESCO
URN
etd-09192013-153720
Title
Leggi zero-uno per grafi random e tecniche di amalgamazione
Struttura
MATEMATICA
Corso di studi
MATEMATICA
Commissione
relatore Prof. Berarducci, Alessandro
Parole chiave
  • amalgamation
  • zero-one law
  • random graph
Data inizio appello
16/09/2013;
Consultabilità
completa
Riassunto analitico
Lo studio dei grafi random, iniziato nel 1960 con un fondamentale articolo di Erdős e Rényi, si è dimostrato un terreno di ricerca molto fertile. Il grafo random G(n, p) è un grafo su n vertici ottenuto congiungendo ciascuna coppia di vertici indipendentemente con probabilità p. Diremo che una successione p: ω → [0,1] soddisfa la legge zero-uno se, per ogni enunciato del primo ordine nel linguaggio dei grafi σ, la probabilità che G(n, p(n)) soddisfi σ tende a 0 oppure a 1 quando n → ∞. I risultati più significativi in questo ambito sono la legge zero-uno di Fagin (1976) e quella di Shelah e Spencer (1988).<br>D’altra parte, le tecniche di amalgamazione hanno creato un gran numero di esempi e controesempi in teoria dei modelli. L’idea è di produrre, a partire da opportune classi di strutture finite, una “struttura limite” numerabile. La costruzione originale, dovuta a Fraïssé, è stata in seguito modificata e generalizzata da Hrushovski e molti altri.<br>Nel 1997, Baldwin e Shelah uniscono queste due linee di ricerca a prima vista incorrelate. Motivati da questo fatto, presenteremo le tecniche di amalgamazione di Fraïssé e di Hrushovski, dimostreremo le due leggi zero-uno enunciate sopra e soprattutto metteremo in evidenza l’interazione tra questi due mondi.
File