Svi smo bili tamo: buljili u test iz matematike sa problemom koji izgleda nemoguće rešiti. Šta ako je pronalaženje rešenja za problem trajalo skoro čitav vek? Za matematičare koji se bave Remzijevom teorijom, ovo je u velikoj meri slučaj. U stvari, mali napredak je postignut u rešavanju Remzijevih problema od 1930-ih.
Istraživači sa Univerziteta u Kaliforniji u San Dijegu Žak Verstret i Sem Mateus pronašli su odgovor na r(4,t), dugogodišnji Ramzijev problem koji decenijama zbunjuje svet matematike.
U matematičkom jeziku, grafik je niz tačaka i linija između tih tačaka. Remzijeva teorija sugeriše da ako je grafik dovoljno velik, garantovano ćete pronaći neku vrstu poretka unutar njega — ili skup tačaka bez linija između njih ili skup tačaka sa svim mogućim linijama između njih (ovi skupovi se nazivaju „klike“). Ovo je zapisano kao r(s,t) gde su s tačke sa pravima, a t tačke bez pravih.
Za one od nas koji se ne bave teorijom grafova, najpoznatiji Remzijev problem, r(3,3), ponekad se naziva „teorema o prijateljima i strancima“ i objašnjava se kao zabava: u grupe od šest ljudi, naći ćete najmanje tri osobe koje se svi poznaju ili tri osobe koje se svi ne poznaju. Odgovor na r(3,3) je šest.
„To je prirodna činjenica, apsolutna istina“, kaže Verstrete. „Nije važno kakva je situacija ili koju šestoricu ljudi izaberete – naći ćete tri osobe koje se svi poznaju ili tri osobe koje se ne poznaju. Možda ćete moći da pronađete više, ali ste garantovano da će u jednoj ili drugoj kliki biti najmanje tri“.
Šta se dogodilo nakon što su matematičari otkrili da je r(3,3) = 6? Naravno, želeli su da znaju r(4,4), r(5,5) i r(4,t) gde je broj tačaka koje nisu povezane promenljiv. Rešenje za r(4,4) je 18 i dokazano je korišćenjem teoreme koju su kreirali Paul Erdos i George Szekeres 1930-ih.
Trenutno je r(5,5) još uvek nepoznato.
Zašto je nešto tako jednostavno za navesti tako teško rešiti? Ispostavilo se da je komplikovanije nego što se čini. Recimo da ste znali da je rešenje za r(5,5) negde između 40–50. Ako biste počeli sa 45 poena, trebalo bi da razmotrite više od 10 234 grafikona.
„Pošto je ove brojke tako ozloglašeno teško pronaći, matematičari traže procene“, objasnio je Verstrete. „To je ono što smo Sem i ja postigli u našem nedavnom radu. Kako da pronađemo ne tačan odgovor, već najbolje procene o tome koliki bi mogli biti ovi Remzijevi brojevi?“
Učenici matematike rano uče o Remzijevim problemima, tako da je r(4,t) bio na Verstreteovom radaru veći deo njegove profesionalne karijere. U stvari, on je prvi put video problem u štampi u Erdošu o grafovima: Njegovo nasleđe nerešenih problema, koje su napisala dva profesora UC San Dijega, Fan Čung i pokojni Ron Grejem. Problem je pretpostavka Erdoša, koji je ponudio 250 dolara prvoj osobi koja bi mogla da ga reši.
„Mnogi ljudi su razmišljali o r(4,t)—to je otvoren problem više od 90 godina“, rekao je Verstraete. „Ali to nije bilo nešto što je bilo na čelu mog istraživanja. Svi znaju da je teško i svi su pokušavali da to shvate, tako da ako nemate novu ideju, nećete nigde stići.“
Onda je pre otprilike četiri godine Verstrete radio na drugom Ramzijevom problemu sa matematičarem sa Univerziteta Ilinois-Čikago, Dhruvom Mubajijem. Zajedno su otkrili da pseudoslučajni grafovi mogu unaprediti trenutno znanje o ovim starim problemima.
Godine 1937. Erdoš je otkrio da korišćenje nasumičnih grafova može dati dobre donje granice za Remzijeve probleme. Ono što su Verstrate i Mubaii otkrili je da uzorkovanje iz pseudoslučajnih grafova često daje bolje granice za Remzijeve brojeve od nasumičnih grafova. Ove granice — gornja i donja granica mogućeg odgovora — sužile su opseg procena koje su mogli da naprave. Drugim rečima, bili su sve bliže istini.
U 2019. godini, na radost sveta matematike, Verstrete i Mubaji su koristili pseudoslučajne grafove da reše r(3,t). Međutim, Verstrete se borio da napravi pseudoslučajni graf koji bi mogao da pomogne u rešavanju r(4,t).
Počeo je da se bavi različitim oblastima matematike van kombinatorike, uključujući konačnu geometriju, algebru i verovatnoću. Na kraju je udružio snage sa Mattheusom, postdoktorskim naučnikom u njegovoj grupi čija je pozadina bila u konačnoj geometriji.
Ispostavilo se da se pseudoslučajni graf koji nam je trebao može naći u konačnoj geometriji“, naveo je Verstrete. „Sam je bio savršena osoba koja je došla i pomogla da izgradimo ono što nam je potrebno.“
Kada su imali pseudoslučajni graf na mestu, još uvek su morali da odgonetnu nekoliko matematičkih delova. Trebalo je skoro godinu dana, ali su na kraju shvatili da imaju rešenje: r(4,t) je blizu kubične funkcije od t. Ako želite zabavu na kojoj će uvek biti četvoro ljudi koji se svi poznaju ili ljudi koji se svi ne poznaju, biće vam potrebno otprilike t3 ljudi. Postoji mala zvezdica (zapravo o) jer, zapamtite, ovo je procena, a ne tačan odgovor. Ali t3 je veoma blizu tačnog odgovora.
Nalazi se trenutno razmatraju u Annals of Mathematics. Preprint se može pogledati na arXiv.
„Zaista su nam bile potrebne godine da to rešimo“, rekao je Verstret. „I bilo je mnogo puta kada smo bili zaglavljeni i pitali se da li ćemo to uopšte moći da rešimo. Ali nikada ne treba odustati, bez obzira koliko dugo treba.“
Verstrete naglašava važnost istrajnosti — nešto na šta često podseća svoje učenike. „Ako otkrijete da je problem težak i da ste zaglavljeni, to znači da je to dobar problem. Fan Čung je rekao da dobar problem uzvrati. Ne možete očekivati da će se samo otkriti.“
Verstrete zna da je takva uporna odlučnost dobro nagrađena: „Pozvala me je Fan i rekla da mi duguje 250 dolara.“
