teoria lui ramsey

Teoria lui Ramsey

ianuarie 2015

Teoria lui Ramsey

Introducere

Teoria lui Ramsey = teorie referitoare la studiul obiectelorcombinatoriale si a conditiilor care se ocupa cu distributiasubmultimilor de elemente ale unei multimi.

Numita dupa matematicianul si filozoful englez Frank P.Ramsey (1903-1930).Rezultate semnificative au fost descoperite ulterilor de P.Erdos.In prezent: tema activa de cercetare ın TGC: numeroaseprobleme nerezolvate ınca.

Problema grupului de persoane ıntrunite:Care este numarul minim R(m, n) de persoane care trebuieinvitate la o ıntrunire, pentru a fi siguri ca una din urmatoareleconditii are loc:

1 ori exista un grup de m persoane care se cunosc toate ıntre ele2 ori exista un grup de n persoane ın care nimeni nu se cunoaste

cu nimeni.

Teoria lui Ramsey

Notiuni preliminare

O 2-colorare a muchiilor unui graf G este o functie careatribuie o culoare din o multime de 2 culori la toate muchiilelui G .

Exemplu (O 2-colorare a lui K5)•

••

••

Pentru doua numere pozitive date p si q, numarul Ramsey (clasic)R(p, q) asociat lor este cel mai mic ıntreg n astfel ıncat orice2-colorare a lui Kn cu rosu si albastru sa contina un subgraf Kp

rosu, sau un subgraf Kq albastru.

Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Teoria lui Ramsey

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?

Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Teoria lui Ramsey

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?

Intrebare: care este valoarea lui R(1, q)?

Teoria lui Ramsey

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Teoria lui Ramsey

Numere RamseyExemplu: R(2, 4)

Fapt: R(2, 4) = 4.Demonstratie. Conform definitiei, R(2, 4) ≥ 2.R(2, 4) ≥ 4 deoarece existenta urmatoarelor 2-colorari de muchiiindica faptul ca R(2, 4) 6∈ {2, 3}.

• • • •

•

K2 K3

Orice colorare rosu-albastru a lui K4 contine fie un K2 rosu sau unK4 albastru deoarece:

Daca exista o muchie rosie, exista un subgraf K2 rosu.

Altfel, toate muchiile sunt albastre, deci graful ınsusi este unsubgraf K4 albastru.

Teoria lui Ramsey

Exercitii

1 Cate 2-colorari diferite (modulo simetrii) are K3? K4? K5?K10?

2 Dati o demonstratie simpla a faptului ca R(1, k) = 1 pentrutoti ıntregii pozitivi k.

3 Dati o demonstratie simpla a faptului ca R(2, k) = k pentrutoti ıntregii k ≥ 2.

4 Explicati de ce, pentru totii ıntregii pozitivi p si q are locR(p, q) = R(q, p).

5 Daca 2 ≤ p′ ≤ p si 2 ≤ q′ ≤ q, demonstrati caR(p′, q′) ≤ R(p, q). Mai mult, egalitatea R(p′, q′) = R(p, q)are loc ın acest caz daca si numai daca p′ = p si q′ = q.

Teoria lui Ramsey

O problema Ramsey clasica

Cate persoane trebuiesc invitate la o petrecere a.ı. sa existecel putin un grup de 3 persoane care se cunosc toti ıntre ei,sau un grup de 3 persoane ın care nimeni nu se cunoaste cunimeni?

Sau, ın teoria lui Ramsey: Care este valoarea minima a lui na.ı. orice colorare rosu-albastru a muchiilor lui Kn sa continafie un K3 rosu sau un K3 albastru?

. Altfel spus, care este valoarea lui R(3, 3)?

Teoria lui Ramsey

O problema Ramsey clasica

Teorema

R(3, 3) = 6.

Demonstratie. R(3, 3) > 5 deoarece 2-colorarea lui K5 de mai jos nucontine nici un K3 rosu si nici un K3 albastru.

K5:

•

••

••

K6:

v

x

y

z

•

•

Subcazul 1: toate muchiile (x,y),(x,z),(y,z) sunt albastre

⇒ exista un K3 albastru

Subcazul 2: cel putin una din muchiile (x,y),(x,z),(y,z) este rosie

⇒ exista un K3 rosu

Fie o colorare rosu-albastru a muchiilor lui K6, si v unul din noduri.

I v este incident la 5 muchii.I Conform Principiului Porumbelului, fie v este incident la ≥ 3 muchiirosii, fie v este incident la ≥ 3 muchii albastre.

Putem presupune ca, ın general, v este incident la 3 muchii rosii (v , x),

(v , y), (v , z).

Teoria lui Ramsey

Alta problema Ramsey

Teorema

R(3, 4) = 9.

Demonstratie. 2-colorarea lui K8 de mai jos nu contine nici un K3

rosu si nici un K4 albastru, deci R(3, 4) > 8.

•

••

•

•

••

•

Vom demonstra ca R(3, 4) ≤ 9 stiind ca R(2, 4) = 4 si R(3, 3) = 6.Sa presupunem ca muchiile lui G = Kn (n ≥ 9) au fost colorate curosu-albastru, si fie v un nod al lui G . Distingem 3 cazuri:

(vezi slide-urile urmatoare.)

Teoria lui Ramsey

Teorema: R(3, 4) = 9Demonstratia cazului 1: v este incident la ≥ 4 muchii rosii

Fie S := multimea nodurilor incidente la v cu o muchie rosie.

•v

•

•

•

•

R(2, 4) = 4 si |S | ≥ 4⇒ fie S are un K2 rosu sau un K4 albastru.Prima posibilitate implica faptul ca G are un K3 rosu, iar a douaimplica faptul ca G are un K4 albastru.

Teoria lui Ramsey

Teorema: R(3, 4) = 9Demonstratia cazului 2: v este incident la ≥ 6 muchii albastre

Fie T :=multimea nodurilor incidente la v cu o muchie albastra.

•v

••••••

|T | = 6 si R(3, 3) = 6⇒ T contine un K3 rosu sau albastru.Primul caz implica faptul ca G are un K3 rosu. In cazul al doileaavem situatia ilustrata mai jos ⇒ G contine un K4.

•v

•

•

••••

Teoria lui Ramsey

Teorema: R(3, 4) = 9Demonstratia cazului 3: v este incident la < 4 muchii rosii si la < 6 muchii albastre

Fie T :=multimea nodurilor incidente la v cu o muchie albastra.Deoarece presupunem ca G are ≥ 9 noduri, trebuie ca G sa aibeexact 9 noduri ⇒ v este incident la 3 muchii rosii si 5 albastre.Deoarece v a fost ales arbitrar, putem presupune ca aceastaproprietate are loc pentru toate nodurile lui G .

⇒ subgraful rosu al lui G are 9 noduri, si fiecare nod are gradul3. Aceasta situatie este imposibila deoarece orice graf are unnumar par de noduri cu grad impar.

Teoria lui Ramsey

Numere Ramsey

Mai jos sunt indicate toate valorile cunoscute de numere Ramsey:

R(1, k) = 1,R(2, k) = k ,

R(3, 3) = 6,R(3, 4) = 9,R(3, 5) = 14,R(3, 6) = 18,R(3, 7) = 23,R(3, 8) = 28,R(3, 9) = 36,

R(4, 4) = 18,R(4, 5) = 25.

In general, determinarea valorilor exacte ale numerelor Ramseyeste extrem de dificila.

Teoria lui Ramsey

Limite cunoscute

Teorema (Erdos si Szekeres)

Daca p ≥ 2 si q ≥ 2 atunci R(p, q) ≤ (p + q − 2)!

(p − 1)!(q − 1)!.

Teorema

Daca p ≥ 2 si q ≥ 2, atunci R(p, q) ≤ R(p − 1, q) + R(p, q − 1).

Teorema

Pentru orice q ≥ 3, R(3, q) ≤ q2 + 3

2.

Teorema (Erdos)

Daca p ≥ 3 atunci R(p, p) > b2n/2c.

Teoria lui Ramsey

Exercitii

1 Sa se demonstreze ca R(3, 5) ≥ 14. Graful urmator esteextrem de util.

K13

••

•

•

•

•• •

•

•

•

•

•

2 Folositi a doua teorema de pe slide-ul precedent ın combinatiecu rezultatul din exercitiul precedent pentru a demonstra caR(3, 5) = 14.

3 Folositi a doua teorema de pe slide-ul precedent pentru ademonstra teorema a treia.

Teoria lui Ramsey

Teoria lui Ramsey pentru grafuri

Generalizare a teoriei clasice a lui Ramsey.

Definitie

Numarul Ramsey R(G ,H) asociat la doua grafuri G si H estevaloarea minima a lui n a.ı. orice colorare rosu-albastru a muchiilorlui Kn contine fie o copie rosie a lui G sau o copie albastra a lui H.

Remarca

In acest context, numarul Ramsey clasic R(p, q) coincide cuR(Kp,Kq).

Teorema

Daca G este un graf de ordin p iar H un graf de ordin q, atunciR(G ,H) ≤ R(p, q).

Demonstratie. Evident.

Teoria lui Ramsey

Teoria lui Ramsey pentru grafuriO margine inferioara pentru R(G ,H)

Numarul cromatic χ(G ) al unui graf G este cel mai mic numark astfel ıncat G este k-colorabil. Acest lucru ınseamna ca:

I folosim k culori pentru nodurile lui G .I nodurile adiacente ın G au culori diferite.

C (H) = ordinul (adica numarul de noduri) al celei mai maricomponente conexe a grafului H.

Teorema urmatoare indica o relatie ıntre R(G ,H), numarulcromatic χ(G ) al lui G , si marimea C (H) a celei mai maricomponente conexe a lui H:

Teorema

R(G ,H) ≥ (χ(G )− 1)(C (H)− 1) + 1.

Teoria lui Ramsey

O margine inferioara pentru R(G ,H)

Teorema

R(G ,H) ≥ (χ(G )− 1)(C (H)− 1) + 1.

Demonstratie. Fie m = χ(G )− 1 si n = C (H)− 1. Fie S graful Km·nformat din m copii ale lui Kn toate muchiile posibile ıntre copii. Apoi secoloreaza albastru muchiile din fiecare copie a lui Kn, si rosu toatecelelalte muchii.

S :

Kn

Kn

Kn

Kn

Nu exista copie albastra a lui C(H) ın S fiindca C(H) aren + 1 noduri si nu intra ın nici un Kn⇒ nu poate exista o copie albastra a lui H ın S.

Nu exista nici o copie rosie a lui G ın S fiindcadaca coloram fiecare copie a lui Kn ın S cu o culoare diferitaatunci producem o m-colorare a lui G .Dar G nu este m-colorabil deoarece χ(G) = m + 1.

S este prea mic: avem nevoie de

p > |S | = m · n = (χ(G )− 1)(C (H)− 1) noduri pentru a garanta

existenta unei copii albastre a lui H sau a unei copii rosii a lui G ın Kp.

Teoria lui Ramsey


Teorema

Daca Tm este arbore cu m noduri atunci R(Tm,Kn) = (m−1)(n−1) + 1.

Demonstratie. Rezultatul are loc pt. m = 1 sau n = 1. De acumıncolo presupunem m ≥ 2 si n ≥ 2.Afirmatia A. R(Tm,Kn) ≥ (m − 1)(n − 1) + 1.

Km−1

Km−1

Km−1

Km−1

Pt. a demonstra acest lucru, fie K(m−1)(n−1) format din n − 1 copii rosiiale lui Km−1, si toate muchiile posibile dintre copii colorate albastru.Nu poate exista nici un Tm rosu si nici un Kn albastru⇒ Are locafirmatia A.Afirmatia B. R(Tm,Kn) ≤ (m − 1)(n − 1) + 1.

O demonstratie a acestei afirmatii este ın [Harris et al. 2008]Teoria lui Ramsey


Teorema

Daca Tm este un arbore de ordin m si daca m − 1 divide n − 1atunci R(Tm,K1,n) = m + n − 1.

In teorema de mai jos, mK2 reprezinta graful format din m copii ale lui

K2, iar n K2 are o semnificatie similara.

Teorema

Daca m ≥ n ≥ 1 atunci R(mK2, n K2) = 2m + n − 1.

Teoria lui Ramsey

Exercitii

1 Sa se calculeze R(P3,P3).

2 Sa se calculeze R(P3,C4).

3 Sa se calculeze R(C4,C4).

4 Demonstrati ca R(K1,3,K1,3) = 6.

5 Demonstrati ca R(2K3,K3) = 8.

Reamintim ca

Cn reprezinta ciclul cu n noduri.

Km,n este graful bipartit complet dintre doua multimi X si Ycu cardinalitatile |X | = m, |Y | = n. Multimea de muchii aacestui graf este E = {(x , y) | x ∈ X , y ∈ Y }.Pn este o cale prin n noduri.

Teoria lui Ramsey

teoria lui ramsey

Documents