Problem Ramseya, taki jak r(4,5), można łatwo sformułować, ale jak pokazano na tym wykresie, możliwe rozwiązania są prawie nieograniczone.
Matematycy z Uniwersytetu Kalifornijskiego (UC) w San Diego, Jacques Verstraete i Sam Mattheus, rozwiązali zagadkowy problem teorii Ramseya, w którego rozwikłaniu postęp był niewielki od czasu, gdy wielki Paul Erdös dokonał pewnych przełomów w 1937 roku. Trafnie, dość złożona teoria Ramseya – gałąź gry liczbowej zajmująca się porządkiem w strukturach, nazwana na cześć brytyjskiego matematyka i filozofa Franka P. Ramseya – jest najczęściej opisywana w kontekście partii.
Najbardziej znany problem w matematycznym zakątku teorii grafów — r(3,3), często nazywany twierdzeniem o przyjaciołach i nieznajomych, zakłada, że w grupie sześciu osób znajdziesz co najmniej trzy osoby, z których każda zna jeszcze jednego lub trzech, którzy się nie znają. Odpowiedź na r(3,3) najwyraźniej brzmi sześć.
„To fakt natury, absolutna prawda” – powiedział Verstraete. „Nie ma znaczenia, jaka jest sytuacja ani które sześć osób wybierzesz – znajdziesz trzy osoby, które się znają, lub trzy osoby, które się nie znają. Być może uda ci się znaleźć więcej, ale nie gwarantujemy, że za jednym lub drugim kliknięciem będą co najmniej trzy.”
Po znalezieniu r(3,3) umysły matematyczne szukały odpowiedzi na kolejne problemy: r(4,4), r(5,5) i r(4,t), gdzie liczba punktów, które nie są połączone, jest różna.
Co się stało, gdy matematycy odkryli, że odpowiedzią na r(3,3) jest 6?
Naturalnie chcieli poznać rozwiązania dla r(4,4), r(5,5) i r(4,t), gdzie liczba niepołączonych punktów jest zmienna. Erdös i George Szekeres odkryli, że odpowiedź na r(4,4) brzmiała 18 w ubiegłym wieku. Tymczasem r(5,5) jest nadal nieznane.
„Wiele osób myślało o r(4,t) – to otwarty problem od ponad 90 lat” – powiedział Verstraete. „Ale nie to było głównym tematem moich badań. Wszyscy wiedzą, że to trudne i wszyscy próbowali to rozgryźć, więc jeśli nie masz nowego pomysłu, prawdopodobnie do niczego nie dojdziesz”.
Chociaż na pierwszy rzut oka może się wydawać, że nie jest to problem, którego rozwiązanie zajęłoby prawie 100 lat, w teorii grafów wygląda na to, że jest to mylące. Na przykład, jeśli rozwiązując r(5,5), wiedziałbyś, że odpowiedź mieści się w przedziale od 40 do 50, i zacząłeś od 45 punktów na wykresie, do zbadania byłoby 10234 wykresów.
„Ponieważ te liczby są niezwykle trudne do znalezienia, matematycy szukają szacunków” – wyjaśnił Verstraete. „To właśnie osiągnęliśmy z Samem w naszej ostatniej pracy. «Jak znaleźć niedokładną odpowiedź, ale najlepsze szacunki dotyczące tych liczb Ramseya?»”
Verstraete po raz pierwszy dowiedział się o r(4,t) w książce od Erdösa w Graphs: His Legacy of Unsolved Problems, napisanej przez profesorów Uniwersytetu Kalifornijskiego w San Diego, Fan Chunga i zmarłego Rona Grahama. Problem wynika z przypuszczeń Erdösa, który zaoferował 250 dolarów pierwszej osobie, która go rozwiąże. Wyobrażamy sobie, że oferta 250 dolarów z lat trzydziestych XX wieku mogła być bardziej „satysfakcjonująca” niż w 2023 roku.
Chociaż Verstraete’owi już od jakiegoś czasu chodziło po głowie r(4,t), dopiero około cztery lata temu, pracując z innym matematykiem nad innym problemem, dokonał przełomu w zakresie grafów pseudolosowych, które przybliżałyby go do rozwiązania zagadki problemu Ramseya.
W 2019 roku Verstraete i matematyk Dhruv Mubayi rozwiązali r(3,t), ale to było wszystko, co im się udało. Dopiero gdy nawiązał współpracę z Mattheusem, który ma doświadczenie w geometrii skończonej, marzenie o rozwiązaniu kolejnego problemu zaczęło wyglądać, jakby mogło stać się rzeczywistością.
„Okazało się, że potrzebny nam graf pseudolosowy można znaleźć w skończonej geometrii” – stwierdził Verstraete. „Sam był idealną osobą, która mogła przyjść z pomocą w zbudowaniu tego, czego potrzebowaliśmy”.
Nadal zajęło to prawie rok, ale znaleziono rozwiązanie r(4,t): Zasadniczo, aby zorganizować imprezę, na której zawsze będą cztery osoby, które się znają, lub t osoby, które się nie znają, wymagałoby to obecności około 3 osób. (W przybliżeniu, bo to nie jest dokładnie trzy.)
„Rozwiązanie tego problemu naprawdę zajęło nam lata” – stwierdził Verstraete. „I wiele razy utknęliśmy i zastanawialiśmy się, czy w ogóle uda nam się rozwiązać ten problem. Ale nigdy nie należy się poddawać, bez względu na to, ile czasu to zajmie”.
Matematycy nie powiedzieli, czy pracują nad rozwiązaniem r(5,5), ponieważ w międzyczasie czekają, aż ich badania zostaną zweryfikowane i zaakceptowane.
„Jeśli stwierdzisz, że problem jest trudny i utkniesz, oznacza to, że jest to dobry problem” – powiedział Verstraete. „Fan Chung powiedział, że dobry problem wraca. Nie możesz oczekiwać, że po prostu się ujawni”.
„Dostałem telefon od Fan, że jest mi winny 250 dolarów” – dodał. Niestety, opłata dla znalazców z lat 30. XX w. nie uwzględniała inflacji.
Recenzja badania została opublikowana w czasopiśmie Annals of Mathematics.
➔ Obserwuj nas w Google News, aby być na bieżąco!
źródło: Uniwersytet Kalifornijski w San Diego | New Atlas
Od 2005 roku zajmuję się komunikacją internetową i e-marketingiem, jestem pasjonatem urządzeń mobilnych oraz nowych technologii – i nie waham się ich używać.