Main tools of the probabilistic method
with applications in graph theory
Attività formativa - Yuri Faenza
Supervisore: Prof. B. Scoppola
CdLS in Ingegneria dei Modelli e dei Sistemi
19 settembre 2006
Indice





Il metodo probabilistico
Linearità dell’aspettazione
Il metodo del momento primo
Il metodo del momento secondo
Il lemma locale di Lovàsz
Il metodo probabilistico
Fine: dimostrare l’esistenza di un oggetto con specifiche
proprietà
Tecnica: Definire un adeguato spazio di probabilità, e
dimostrare che a tale oggetto è associata una probabilità
positiva
Origini: Szele (’43), Erdos (’47)
Maggiori Contributi: Erdos, Lovàsz, Janson, Alon, Spencer
Applicazioni: Teoria dei grafi, Geometria Computazionale,
Informatica Teorica
Il metodo probabilistico (2)
Pro:
 ottiene “facilmente” risultati difficili da raggiungere
deterministicamente;
 tecnica probabilistica, risultato deterministico.
 permette di costruire oggetti di grandi dimensioni, non
strutturati e generali;
Contro:
 raramente costruisce esempi espliciti.
Notazione e definizioni
Variabili aleatorie
Grafo con n vertici ed e archi
se
Numero cromatico di G
Massimo insieme indipendente di G
Linearità dell’aspettazione
Thr. (Szele): Esiste un torneo T con n giocatori ed almeno
sentieri hamiltoniani
Torneo
Dim.
Sentiero hamiltoniano
: # sentieri hamiltoniani
: permutazione degli n giocatori
se è un sentiero hamiltoniano, cioè se
altrimenti
Linearità dell’aspettazione (2)
Thr. (Erdos): Per ogni k,l > 0 esiste un grafo G con lunghezza del ciclo
più breve pari ad l e
Dim.
fissi
Si
e si assegni ogni arco di G in modo indipendente, con
probabilità
numero di cicli di lunghezza al più l
se l’insieme A forma un ciclo, |A| = i
altrimenti
Linearità dell’aspettazione (3)
In particolare:
Posto
1)
2)
Possiamo quindi scegliere n grande abbastanza perché esista G per cui 1) e
2) non sono verificati
Si rimuova da ogni ciclo di lunghezza al più l un vertice, ottenendo
che per quanto visto ha almeno
vertici, ha il più piccolo ciclo di
lunghezza maggiore di l e vale
Il metodo del momento primo
Thr. (Caro & Wei): Per ogni grafo G(V,E) vale
Dim.
Si consideri un ordinamento di V scelto con probabilità uniforme
Il metodo del momento primo (2)
v.a. che indica se v è nell’insieme I
v ed iMetodo
suoi vicini
tuttiprimo
la stessa
del hanno
momento
possibilità di avere l’indice più piccolo
I è un insieme indipendente, infatti se per assurdo non lo fosse, esisterebbero
tali che
; ma allora
e
; impossibile
Teorema di Turan
Il metodo del momento secondo
Lemma (Diseguaglianza di Markov)
Dim.
Lemma (Diseguaglianza di Tchebyschev) Per ogni
Dim.
Il metodo del momento secondo (2)
Corollario Sia
non negativa
Dim.
Utilizzo: lower bound sul numero cromatico e proprietà dei
grafi random
Il lemma locale di Lovàsz
Obiettivo: dimostrare che A raro ha probabilità > 0
Con
eventi indipendenti, ciascuno con probabilità (almeno) p
Lemma locale di Lovàsz:
generalizzazione al caso in cui gli eventi che ci interessano sono
“quasi” dipendenti, per provare l’esistenza di eventi rari
Il lemma locale di Lovàsz (2)
Thr (Lll), caso generale:
Il lemma locale di Lovàsz (3)
Thr (Lll), caso simmetrico:
è dipendente da al più altri d eventi
Il lemma locale di Lovàsz (4)
Thr (Alon & Linial): Sia D(V,E) un grafo orientato con minimo
grado uscente
e massimo grado entrante
.
Se
allora D contiene un ciclo orientato,
Grafo Orientato
D(V,E)
semplice
di lunghezza
u
v
Dim.
(u,v)
Si
consideri
un colorazione casuale di V
Grado
entrante/uscente
in cui ogni nodo è colorato in modo uniforme ed indipendente dagli
altri.
Il lemma locale di Lovàsz (5)
Ogni
è indipendente da tutti gli eventi
Tali eventi sono al più
v
tranne quelli per cui vale:
,
è limitata
u
Applichiamo il Lll (caso simmetrico)
Il lemma locale di Lovàsz (3)
Thr (Lll), caso simmetrico:
è dipendente da al più altri d eventi
Il lemma locale di Lovàsz (6)
Partendo da
otteniamo una sequenza
tale che
e
Sia j il minimo intero tale che esista
Allora il ciclo
è quello richiesto