Przełom w piekielnie trudnym problemie matematycznym

Prawie sto lat temu w kombinatoryce wykazano pewien problem, który spędzał sen z powiek matematykom. Jednak udało się dokonać przełomu i doprecyzować górną granicę liczby Ramseya tego piekielnie trudnego zagadnienia.

Prawie sto lat temu w kombinatoryce wykazano pewien problem
Prawie sto lat temu w kombinatoryce wykazano pewien problem123RF/PICSEL

Po pierwsze należy podkreślić, że taki przełom to naprawdę duże wydarzenie w świecie matematyków. Przez 75 lat udało się tego dokonać dopiero po raz trzeci. Problem dotyczy liczby Ramseya, jest to koncepcja matematyczna zwodniczo prosta, jednak jak to w kombinatoryce bywa, sprawy bardzo szybko wymykają się spod kontroli.

Czym jest liczba Ramseya

Liczba Ramseya dotyczy twierdzenia matematycznego Ramseya odnoszącego się do teorii grafów. Jest to minimalna wielkość grupy potrzebna do zapewnienia, że pewna liczba węzłów w tej grupie jest ze sobą połączona.

Najczęściej jest to obrazowane za pomocą przyjęcia.  Ile osób musimy zaprosić na imprezę, aby mieć pewność, że będzie to grupa trzech osób sobie obcych, albo grupa trzech osób sobie znajomych? Odpowiedź wydaje się w tym wypadku oczywista, liczba Ramseya dla 3 wynosi 6. Natomiast żeby mieć pewność, że czteroosobowa grupa składa się z czwórki przyjaciół lub z czwórki obcych sobie ludzi, wtedy liczba gości wzrasta do 18.

Schodki zaczynają się wtedy, gdy chcemy określić liczbę Ramseya dla 5. Jedyną odpowiedzią profesorów matematyki jest określenie przedziału między 43 a 48. Jeżeli zaś liczby zaczynają rosnąć, stopień trudności wskazania rozwiązań wzrasta, ponieważ im więcej składników w sieci, tym więcej możliwych połączeń, a co za tym idzie, więcej struktur dla wynikowego grafu. Powstaje tak wiele możliwości, że znalezienie odpowiedzi może zająć lata.

Osiągnięcie przełomu

W 1935 roku wybitny matematyk Paul Erdös, określił zakres dla dowolnej liczby Ramseya. Odkrył, że górna granica liczby Ramseya dla danej liczby N wynosi 4 do potęgi N. Natomiast dolną granicę udało mu się określić dopiero w 1947 roku, gdzie wynosi ona pierwiastek kwadratowy z 2 do potęgi N. Tym, co zajmuje matematyków w tym problemie to odkryć, jak można zawęzić zakres dostępnych wyników.

Przełomu dokonał profesor matematyki Marcelo Campos z Kalifornijskiego Instytutu Technologicznego, wraz ze współpracownikami. Cała sprawa może nie brzmieć sensacyjnie, jednak w świecie matematyki do bardzo duże osiągnięcie. Pierwszy raz od 1935 roku dokonano przesunięcia górnej granicy. Dopracowano nowy algorytm, dzięki któremu udało im się zawęzić górną granicę z 4 do potęgi N do 3.993 do potęgi N. Nie brzmi to nad wyraz fascynująco, jednak dla matematyków, którzy poświęcili na te obliczenia całe życie, jest to naprawdę coś.  Liczby Ramseya znajdują się w sferze czysto matematycznej i nie znajdują zastosowania w świecie rzeczywistym. Jednak, w latach 80. badano teorię Ramseya w połączeniu z koncepcją zwaną quasi-losowością, która teraz odgrywa dużą rolę w informatyce.

Masz sugestie, uwagi albo widzisz błąd?
Dołącz do nas