Teorema lui Ramsey

În combinatorie , teorema lui Ramsey afirmă că pentru fiecare colorare a marginilor unui grafic complet cu un număr destul de mare de vârfuri este posibil să se găsească un subgraf monocromatic complet.

În cazul în care graficul este colorat doar cu două culori, de exemplu roșu și albastru, teorema lui Ramsey afirmă că în orice caz alese două numere întregi pozitive r și s există un număr întreg R ( r , s ) astfel încât într-un grafic complet cu cel puțin vârfuri R ( r , s ) este întotdeauna posibil, pentru orice colorare, să se găsească un subgraf complet albastru complet cu vârfuri r sau un subgraf complet roșu complet cu vârfuri s . Numărul R ( r , s ) trebuie înțeles ca cel mai mic număr întreg pentru care deține această proprietate și se numește numărul Ramsey .

Teorema lui Ramsey este valabilă și pentru mai mult de două culori: ales un număr c de culori, pentru orice alegere de numere întregi pozitive n ₁ , ..., n _c există un număr R ( n ₁ , ..., n _c ) astfel că în fiecare grafic cu cel puțin R (n _1, ..., n _c) vârfuri este întotdeauna posibil să se găsească, pentru unii i între 1 și c, un subgraf complet cu n _i vârfuri total colorate cu culoarea i.

Teorema lui Ramsey este un rezultat fundamental în combinatorică. Prima versiune a fost dovedită de Frank P. Ramsey și a început ceea ce se numește teoria lui Ramsey .

Exemplu: R (3,3) = 6

În exemplul următor dorim să găsim numărul minim de persoane necesar pentru a ne asigura că apare cel puțin una dintre următoarele două posibilități:

• Trei persoane se cunosc.
• Trei persoane nu au nicio legătură una cu alta.

Dacă considerăm fiecare persoană ca vârful unui grafic complet, putem:

• Colorați marginea care le unește în roșu dacă vă cunoașteți.
• Colorează marginea care le unește în albastru dacă nu sunt cunoscute.

Problema devine atunci pentru a găsi numărul minim de vârfuri necesare pentru a se asigura că există întotdeauna un triunghi (subgraf complet cu 3 vârfuri) total roșu sau total albastru. Prin urmare, încercăm să dăm o valoare numărului Ramsey R (3,3).

Este ușor să arătăm că, în cazul a șase persoane, cele două alternative apar întotdeauna și, prin urmare, numărul Ramsey R (3,3) este mai mic sau egal cu 6. Să luăm un grup de șase persoane, pe care le numim A, B, C, D, E și F și ia în considerare A. Deoarece există alte cinci persoane, se întâmplă întotdeauna că fie A le cunoaște cel puțin trei, fie A nu le cunoaște pe cel puțin trei. Fără pierderea generalității, putem presupune că A știe cel puțin trei, că alegem să fim C, D și F. Dacă cel puțin doi dintre acești trei oameni s-ar cunoaște, de exemplu C cu F, am fi găsit trei persoane , A, C și F care se cunosc (și formează un triunghi roșu în grafic). Dacă, pe de altă parte, aceste trei persoane nu se cunosc, am găsit un grup de trei persoane care sunt complet străine unele de altele (și formează un triunghi albastru în grafic). Orice s-ar întâmpla, prin urmare, una dintre cele două alternative trebuie să devină realitate.

Contraexemplul care arată că R (3,3)> 5.

De fapt, numărul Ramsey R (3,3) este exact egal cu 6: este de fapt posibil să se găsească un grup de 5 persoane în care nu apare nici una dintre cele două alternative. Pentru a face acest lucru, aranjăm cele 5 persoane în jurul unei mese prin rotire și presupunem că fiecare știe doar oamenii care stau lângă ei. În acest fel, toată lumea știe exact doi oameni, iar exact doi oameni îi sunt străini. Nici o alternativă nu apare. Grafic, această construcție poate fi vizualizată ca un grafic în care laturile exterioare sunt toate colorate în roșu, în timp ce laturile interioare sunt toate colorate în albastru. Acest contraexemplu arată că R (3,3) = 6. ^[1]

Numere Ramsey

Numerele R ( r , s ) prezente în teorema lui Ramsey, precum și extensia lor multicoloră, se numesc numere Ramsey. Dovada teoremei în sine oferă o limită superioară pentru fiecare dintre aceste numere, iar limitele inferioare pot fi găsite prin alte metode. (Prima limită inferioară a fost obținută de Paul Erdős folosind o metodă probabilistică). Cu toate acestea, există, în general, o diferență mare între cele două limite, iar valoarea exactă a numărului Ramsey R ( r , s ) este cunoscută doar pentru câteva cazuri.

Este util să rețineți că, deoarece ordinea culorilor nu este importantă, inversarea celor două valori r și s nu modifică numărul Ramsey asociat acestora, adică R ( r , s ) = R ( s , r ) . Mai general, în cazul a mai mult de două culori, orice permutare a valorilor nu modifică numărul Ramsey (de exemplu, R (2,4,7) = R (7,2,4)).

Așa cum s-a descris mai sus, R (3,3) = 6. Este ușor de demonstrat că R ( r , 2) = r pentru toate r (și același lucru este valabil și pentru R (2, r )). De asemenea, sunt cunoscuți R (4,3) = 9 și R (4,4) = 18 și R (3, r ) până la r = 9. Celelalte valori exacte sunt încă necunoscute și se cunosc doar limitele superioare și inferioare. De exemplu, s-a demonstrat că R (5,5) se situează între 43 și 49 (inclusiv).

Tabelul următor descrie valorile numerelor Ramsey cunoscute și, pentru cele necunoscute, cele mai bune limite inferioare și superioare.

Notă

Bibliografie

• Bruce M. Landman, Aaron Robertson, Ramsey Theory on the Integers , American Mathematical Society, 2004, ISBN 0-8218-3199-2 .

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere despre teorema lui Ramsey

linkuri externe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică