Teorema lui Ramsey

Source: http://www.math.grin.edu/~miletijo/museum/ramsey.html

Autor: Joe Mileti

Iată un exemplu. Să presupunem că vă invităm 6 prieteni aleatoriu la o petrecere. Deşi ştiţi toţi prietenii dvs., dacă alege doi dintre prieteni invitaţi, acestea pot sau nu pot au fost introduse. Surprinzator, indiferent care 6 prieteni va invita, veţi fi întotdeauna în măsură să găsească 3 prieteni pe listă, astfel încât între aceste 3, fie:
1) Toate au fost introduse la fiecare alte
2) Nici unul au fost introduse pentru fiecare alte

Asta a fost o gura, asa ca hai sa reformuleze problema într-o altă, mult mai abstract, setarea. Să presupunem că aveţi locul 6 cuie pe o masă, şi vă conectaţi fiecare pereche de cuie, fie cu o bucată de sfoară roşie sau o bucată de sfoară verde(puteti folosi culori diferite pentru diferite perechi). Un alt mod de a stat rezultatul de mai sus este faptul că, indiferent de modul în care conectaţi cuiere, puteţi găsi întotdeauna fie un triunghi roşu(adică 3 cuiere, astfel încât fiecare este conectat la alţii prin intermediul string rosu) sau un triunghi verde.

Opriţi-vă pentru un minut şi să se gândească modul în care această formulare se conectează la situaţia de mai sus. Dacă credeţi că dvs. de 6 prieteni ca cuiere, un şir de roşu de racordare de 2 carlige reprezintă faptul că cei 2 prieteni corespunzătoare au fost introduse, şi un şir de verde conectat 2 cuiere reprezintă faptul că cei 2 prieteni corespunzătoare nu au fost introduse, atunci ambele formulări, spun acelaşi lucru.

Cum ne putem convinge de acest rezultat? Să presupunem că aveţi 6 picioare în faţa ta, şi că fiecare pereche este conectat printr-un şir de caractere fie roşu sau un şir de verde. Alegeţi orice cuier care iti plac. Sunati-l A. Acum A este conectat la alte 5 picioare, fie cu şir roşu sau verde şir, astfel încât între aceste 5, putem alege trei cuie, le numim B, C, şi D, astfel încât AB, AC, AD şi toate au aceeaşi culoare(de către AB ma refer la şirul de conectare picioare A şi B), de principiul sertar. Acum, dacă oricare dintre BC, BD, sau CD-ul au aceeasi culoare ca AB, atunci am terminat(presupunem că BC are aceeasi culoare ca si AB. Apoi triunghiului ABC constă doar o culoare). În caz contrar, fiecare dintre BC, BD, şi CD-ul trebuie să aibă aceeaşi culoare(culoare diferită de cea a AB), şi astfel lucrările triunghiul BCD.

Exerciţiu: Căutaţi un aranjament din 5 cuie, astfel încât fiecare pereche este conectat fie prin şir de culoare roşie sau verde, care nu conţine un singur triunghi de culoare. Prin urmare, 6 este cel mai mic număr putem folosi de mai sus.

Ce se întâmplă aici? Imaginaţi-vă că aţi încercat să vă conectaţi 6 picioare fără să formeze un triunghi o singura culoare. Aşa cum am începe conectarea cu sfoară noastre, nu vrem să utilizaţi o culoare prea mult, deoarece după introducerea suficient şir roşu ne-ar garanta cu siguranţă crearea unui triunghi roşu. În mod similar, nu vrem să loc şir prea mult verde, sau altfel ne-ar face cu siguranţă un triunghi verde. Atunci când ne este permis să se utilizeze atât, ne-am folosi pentru a echilibra noastre, iar argumentele de mai sus arată că 6 carlige este punctul de rupere.

Putem generaliza acest dincolo de o singura culoare, triunghiuri? În limbajul de Teorema lui Ramsey, aceste triunghiuri o singura culoare se numesc omogene(sensul structură uniformă sau a compoziţiei) sau monocromatice(adică de o culoare). Astfel, putem spune că trei cuie forma o colectie monocromatica în cazul în care triunghiul format de cele trei este format din doar o singură culoare. Ce zici de o colectie monocromatica din 4 cuie? Având în vedere 4 cuiere, există 6 corzi care le conecta la alte fiecare. Prin urmare, ele nu fac doar un obiect 4-verso, dar de fapt un obiect 4-verso cu 2 diagonale. Noi spunem că 4 cuie forma o colectie monocromatica dacă fiecare din aceste 6 corzi au aceeasi culoare. În mod similar, spunem că cuie k formeaza o colectie monocromatica dacă fiecare din siruri de caractere de racordare de 2 cuie în colectare care au aceeaşi culoare.

Prin raţionament similar(deşi destul de un pic mai complicat), se poate argumenta că, indiferent de modul în care conectaţi cu 18 cuie cu sfoară roşu şi verde, puteţi găsi o colecţie monocromatica de 4 cuie. Declarată în formula noastră originală, putem exprima acest lucru, spunând că, dacă va invita 18 prieteni la o petrecere, atunci puteţi fi siguri că puteţi alege 4 prieteni, astfel încât între aceste 4, fie ca toate au fost introduse unele de altele, sau niciuna dintre ele au fost introduse unele de altele. În plus, 18 este pragul, ceea ce înseamnă că puteţi găsi un aranjament de 17 cuie, fără o colectie monocromatica de 4 cuie.

O versiune de state Teorema lui Ramsey că, indiferent ce număr de k pe care o alegeţi, puteţi găsi un număr de n astfel încât având în vedere orice aranjament de cuie n, trebuie să existe o colecţie de cuie k monocromatica. Vom nota cele mai mici n astfel că lucrează pentru un k dat de R(k). Rezultatele de mai sus poate fi declarat mai succint prin a spune că R(3)= 6 şi R(4)= 18. Este uşor să vedem că R(1)= 1(dat doar 1 cuier, nu există bucăţi de sfoară, astfel încât aceasta face o colecţie de monochrome pentru motive de vid) şi R(2)= 2(Dacă aveţi doar 2 cuie, există doar bucată de sfoară, astfel încât cele 2 picioare forma o colectie monochramtic). Poate surprinzător, nimeni nu ştie valoarea lui R(k) pentru orice k mai mare de 4. Cele mai bune rezultate cunoscut în prezent de stat faptul că R(5) este undeva între 43 şi 49(inclusiv) şi R(6) este undeva între 102 şi 165. S-ar putea întreba de ce, având în vedere puterea de calcul incredibil la dispoziţia noastră, nu ne putem căuta pur şi simplu, prin toate modalităţile de şir de 43 de cuie prin 49 carlige pentru a găsi valoarea reală a R(5). Cu toate acestea, se poate calcula că există 2 ^ 903(un numar care are 272 cifre zecimale!) Modalităţi de a aranja şir roşu şi verde între 43 cuie, care este un număr dincolo de intelegerea ordinare(oamenii de ştiinţă estimează că există aproximativ 80 de cifre în numărul de electroni din univers). Prin folosirea simetrie, o pot reduce drastic numărul de astfel de aranjamente un computer ar trebui să se uite la, dar chiar dacă am doar a trebuit să examineze 1 din fiecare 1000 miliarde configuraţii, ne-ar fi lăsat cu peste 2 ^ 864 aranjamente(o număr care are 261 cifre!). Estimarea valorile R(k) necesită ingeniozitate matematice în plus faţă de calculele brute force.

Paul Erdos, una dintre cele mathematcians mari ale secolului XX, glumea odată că dacă un străin fiind cerea ca noi spunem că valoarea R(5) sau suferă distrugerea Pământului, atunci ar trebui să stabilească imediat toate matematicieni şi computerelor să se sarcina de calcul al valorii. Cu toate acestea, în cazul în care a cerut valoarea lui R(6), atunci ar trebui să încercăm să o distrugă înainte de a ne distrus.