Proboj u teoriji Ramseyja: matematičari i AI približili red u haosu

Većinu prošlog veka matematičari su pokušavali da razotkriju granice teorije Ramseyja — oblasti koja proučava kako se poredak pojavljuje unutar naizgled haotičnih sistema. Napredak je često bio spor, ali nedavni preprint Domagoja Bradača i dalja doterivanja koja je predložio model za rezonovanje iz OpenAI donose značajan pomak i jasniji uvid u prelaz između slučajnosti i strukture u grafovima.

U matematici se posmatraju grafovi: mreže tačaka (vrhova) povezanih ivicama. Kako graf raste, neizbežno će sadržati ili potpuno povezanu grupu vrhova — kliku — ili veliku grupu vrhova bez ikakvih međusobnih veza — nezavisnu skupinu. Ramsey brojevi R(s,t) kvantifikuju koliko veliki graf može da bude pre nego što će sigurno sadržati kliku veličine s ili nezavisnu skupinu veličine t.

Bradačev rad, objavljen na serveru arXiv, znatno je zaoštio donje granice za tzv. off-diagonal Ramsey brojeve — slučajeve u kojima su s i t vrlo različiti (na primer R(3,1000)). Metoda kombinuje pažljivo izgrađen, geometrijski i algebarski strukturiran veliki graf i probabilistički izbor podgrafa željene veličine. Nakon toga se strateški uklanja mala količina problematičnih vrhova kako bi se obnovila tražena svojstva bez značajnog gubitka veličine.

Probabilistička metoda i geometrijska struktura

Glavni alat u ovom radu je probabilistička metoda: umesto izgradnje konkretnog primera, dokazuje se postojanje tako što se pokaže da nasumično izabrani objekat ima nenultu verovatnoću da zadovolji uslove. Bradač prvo koristi graf sa jasnom geometrijskom strukturom (što olakšava dokazivanje određenih svojstava), a zatim "zumira" i nasumično bira podgrafove, uklanjajući mali broj problematičnih tačaka.

"U idealnom svetu ja bih samo rekao: pogledajte, evo grafa, i to je to", kaže Bradač. "Nažalost, ne znamo kako to da učinimo."

Rezultat je porodica grafova koja može da bude veća nego što se ranije moglo dokazati, a da i dalje izbegava male klike i velike nezavisne skupine. Bradačev pristup dovodi donju granicu gotovo do najbolje poznate gornje granice koja datira iz 1930-ih — do razlike koja sada iznosi samo polilogaritamske faktore.

Uloga veštačke inteligencije

Neobičan deo ove priče je da je prvo značajno poboljšanje došlo ne od drugog matematičara, već od OpenAI-jevog internog modela za rezonovanje. Istraživači iz OpenAI su testirali Bradačev dokaz i model je predložio fino podešavanje koje je dodatno zateglo donju granicu. Zajedno, originalni dokaz i AI-jev predlog sada se poklapaju sa najboljom poznatom gornjom granicom do polilogaritamskih faktora.

Mehtaab Sawhney (OpenAI): "Nismo sistematski pokušavali da unapredimo nove arXiv radove; u ovom slučaju se poklopilo — model je upravo obrađivao srodan problem kada je stigao preprint."

Stručnjaci ističu da AI nije zamenio konceptualni preokret koji je doneo Bradačev pristup, već je doprineo važnom tehničkom poboljšanju. Marcelo Campos (IMPA) napominje da je doterivanje modela zasnovano na istim idejama koje su već bile u izvornom radu.

Šta ovo znači za matematiku

Ovo predstavlja veliki konceptualni pomak u razumevanju prelaza između haosa i reda u teoriji grafova. Iako i dalje postoji sitna tehnička razlika do potpunog zatvaranja problema, mnogi matematičari smatraju da je ovo najbliže što su do sada stigli ka otkriću preciznog rasta off-diagonal Ramsey brojeva. Sledeći koraci podrazumevaju dalju proveru dokaza, moguće formalizacije i potragu za konstruktivnim primerima koji bi ilustrovali postojanje takvih grafova.

Ključne reči: Ramsey brojevi, grafovi, probabilistička metoda, geometrijska konstrukcija, veštačka inteligencija, Domagoj Bradač, OpenAI.