Un mic salt înainte în teoria graficelor

Pe 15 martie, anunţuri interesante ale seminarului au transmis zgomote în domeniul combinatoriei, studiul matematic al numărării. Trei colaboratori au planificat să susțină discuții coordonate în ziua următoare. Julian Sahasrabudhe s-ar adresa matematicienilor din Cambridge, Anglia, în timp ce Simon Griffiths avea să împărtășească știrile la Rio de Janeiro și Marcelo Campos în São Paulo. Toate cele trei discuții prezentau titluri identice și rezumate criptice, în două propoziții, care făceau referire la „progresul recent asupra unei vechi probleme a lui Erdős”. În timp ce Paul Erdős, un matematician maghiar care a murit în 1996, a pozat sute de probleme în timpul carierei sale, combinatoriștii au intuit rapid problema specifică despre care trio-ul plănuia să vorbească. Au circulat zvonuri despre ceva numit numărul Ramsey, una dintre cele mai dificile cantități de calculat în toată matematica.

Numerele Ramsey au generat o întreagă disciplină numită teoria Ramsey, care caută modele inevitabile într-o gamă largă de sisteme.

De exemplu, să presupunem că încercați să răspândiți toate numerele întregi într-un număr de compartimente și doriți să evitați să plasați secvențe de numere uniform distanțate în oricare dintre compartimente. Teoria Ramsey arată că vei eșua (cu excepția cazului în care ai infinit de găleți). Teoria poate fi aplicată la aproape orice lucru pe care îl puteți număra. Lecția sa centrală este că „nu poți crea un sistem complet haotic”, a spus Benny Sudakov, un matematician la Institutul Federal de Tehnologie din Zurich.

Numărul Ramsey cuantifică cât de mare trebuie să fie un exemplu paradigmatic înainte ca anumite modele să apară inevitabil. Dar, în ciuda centralității sale, nimeni nu a fost capabil să calculeze numărul Ramsey pentru toate, cu excepția lui cele mai simple cazuri. Cel mai bun lucru pe care au reușit să facă este să găsească limite (sau limite) a ceea ce ar putea fi. Chiar și atunci, limita superioară stabilită pentru prima dată de Erdős și un colaborator în urmă cu aproape un secol abia se clintise.

Apoi, în cadrul seminariilor din 15 martie și într-o lucrare postată mai târziu în acea seară, cercetătorii au anunțat că au îmbunătățit limita superioară a numărului Ramsey cu o sumă exponențială.

„Am fost dezamăgit”, a spus Yuval Wigderson, un matematician la Universitatea din Tel Aviv, când a auzit despre noul rezultat. „Am tremurat literalmente între o jumătate de oră până la o oră.”

Liniile de partid

Teoria Ramsey pune cel mai frecvent întrebări fie despre numere întregi, fie despre grafice. Un grafic, în acest context, se referă la colecții de puncte numite noduri, conectate prin linii numite muchii, care pot avea proprietăți precum lungimea sau - ca în cazul numerelor Ramsey - culoare.

Un grafic complet este atât complicat, cât și simplu - fiecare nod este conectat la fiecare alt nod. Numărul Ramsey descrie câte noduri trebuie să conțină un grafic complet pentru a fi forțat să aibă o anumită structură. Să presupunem că muchiile unui grafic complet au una dintre cele două culori: roșu sau albastru. Și spuneți că încercați să colorați marginile într-un mod care să evite conectarea unui grup de noduri cu margini de aceeași culoare. În 1930, Frank Ramsey a demonstrat că, dacă un grafic este suficient de mare, devine imposibil să se evite crearea a ceea ce matematicienii numesc o clică monocromatică - un grup de noduri ale căror margini comune sunt fie toate roșii, fie toate albastre.

Cât de mare trebuie să fie, exact, un grafic înainte ca o clică monocromatică să fie forțată să apară? Răspunsul depinde de mărimea clicei. Ramsey a arătat că există un număr, numit acum numărul Ramsey, reprezentând numărul minim de noduri pentru care trebuie să existe o clică monocromatică de o anumită dimensiune, indiferent de modul în care sunt colorate marginile.

Dar dimensiunea numărului Ramsey este greu de stabilit. În 1935, la cinci ani după ce Ramsey a arătat că există, Erdős și George Szekeres au oferit o nouă limită superioară mai strictă privind cât de mare este numărul Ramsey pentru o clică de o anumită dimensiune. Dar de atunci, matematicienii abia au reușit să îmbunătățească calculul lui Erdős și Szekeres.

Pentru a obține o intuiție mai bună a ceea ce înseamnă aceasta, luați în considerare un exemplu clasic, în care nodurile reprezintă invitații la o petrecere. Colorează marginea dintre oricare doi oaspeți în roșu dacă s-au întâlnit înainte și în albastru dacă nu s-au întâlnit. Puteți alege orice dimensiune de clică care vă place — invitați destui oameni la petrecere și nu puteți evita fie să invitați un grup de oameni care se cunosc cu toții (o clică în mai multe sensuri ale cuvântului), fie să invitați un grup de oameni care nu ne-am mai întâlnit până acum.

„Cel mai simplu lucru pe care îl puteți avea într-un grafic este o clică monocromatică”, a spus Maria Chudnovsky, un matematician la Universitatea Princeton. „Este oarecum uimitor că în fiecare grafic uriaș poți găsi unul dintre acestea. Nu este complet clar.”

Primele numere Ramsey sunt relativ simplu de calculat. Să presupunem că doriți să aflați dimensiunea celui mai mic grafic care trebuie să dețină inevitabil o clică de dimensiunea doi sau R(2) pentru matematicieni. Deoarece un grafic complet cu două noduri este doar două noduri conectate printr-o muchie, iar muchia respectivă trebuie să fie roșie sau albastră, R(2) este 2. Mai general, R(k), sau numărul Ramsey al k, este numărul minim de noduri dincolo de care un grafic nu poate evita să conțină o clică de dimensiune k.

Nu este atât de greu să arăți că numărul Ramsey pentru o clică de dimensiunea 3, sau R(3), este 6 (vezi graficul). Dar abia în 1955, R(4) a fost fixat la 18. R(5) rămâne necunoscut - este cel puțin 43 și nu mai mare de 48. Deși aceste numere sunt mici, nu se mai verifică toate culorile posibile. de întrebare, a spus David Conlon de la Institutul de Tehnologie din California. Luați în considerare numărul de colorații pe un grafic complet cu 43 de noduri. „Ai 903 margini; fiecare dintre acestea poate fi colorat în două moduri”, a explicat el. „Deci primești 2⁹⁰³, care este doar astronomic mare.”

Pe măsură ce dimensiunea clicei crește, sarcina de a stabili numărul Ramsey devine doar mai dificilă. Erdős a glumit că războiul total cu extratereștrii pretențioși din punct de vedere matematic ar fi mai ușor decât să încerci descoperă R(6), care este undeva între 102 și 165. Intervalul de incertitudine crește rapid: Conform estimări întocmite de Stanisław Radziszowski, R(10) ar putea fi la fel de mic ca 798 și la fel de mare ca 23,556. Dar obiectivele matematicienilor depășesc cu mult numărul Ramsey de 10. Ei doresc o formulă care să ofere o estimare bună a lui R(k), chiar — sau mai ales — când k este extrem de mare.

„Nu cunosc o persoană din combinatorică care să nu se fi gândit măcar puțin la această problemă”, a spus Wigderson. „Cred că această problemă este cu adevărat specială.”

Ordin în Curte

Frank Ramsey a fost o figură eclectică, strălucitoare, care a murit când avea 26 de ani. Cu doar câteva săptămâni înainte de a muri, el Proceedings of the London Mathematical Society publicat hârtia în care a introdus numerele Ramsey. Lucrarea aceea nici măcar nu era despre grafice, ci despre o problemă de logică matematică. Ramsey a demonstrat că o afirmație care îndeplinește anumite condiții trebuie să fie adevărată cel puțin o parte din timp. Una dintre aceste condiții a fost să existe un „univers” mare de scenarii în care să testeze afirmația. Ca o piatră de temelie către acest rezultat, Ramsey a arătat că numărul Ramsey este finit.

Cinci ani mai târziu, Erdős și Szekeres au arătat că numărul Ramsey de k este mai mic de 4^k. Și la 12 ani după aceea, a arătat Erdős că este mai mare decât aproximativ $latex sqrt{2}^k$. Pentru a face asta, el a calculat șansele ca un grafic cu margini colorate aleatoriu să conțină o clică monocromatică. Această tehnică „probabilistă” a devenit extrem de influentă în teoria grafurilor. De asemenea, a prins R(k) între două stâlpi care cresc exponențial: $latex sqrt{2}^k$ și $latex 4^k$.

Pe măsură ce deceniile au trecut, numeroși matematicieni au încercat să reducă decalajul dintre posibilele valori ale numărului Ramsey. Unii au reușit: în 1975, Joel Spencer a dublat limita inferioară. Și o serie de lucrări de Conlon, Andrew Thomason și Ashwin Sah împins în jos limita superioară cu un factor de aproximativ $latex 4^{log(k)^2}$ până în 2020. Dar, în comparație cu dimensiunile limitelor numărului Ramsey, aceste ajustări au fost mici. Prin contrast, orice reducere la 4 în formula lui Erdős și Szekeres R(k) < 4^k ar fi o îmbunătățire exponențială, în creștere rapidă ca k devine mai mare.

„Pare a fi doar o mică întrebare drăguță”, a spus Rob Morris, matematician la IMPA, Institutul brazilian de matematică pură și aplicată, din Rio de Janeiro, care a fost coautor al noului rezultat împreună cu Campos, Griffiths și Sahasrabudhe. „Este puțin subtil de apreciat. Dar oamenilor le pasă cu adevărat de asta.” Aceasta este posibil o subestimare. „Dacă ar fi dovedit-o în 1936, oamenii ar fi spus: OK, deci care este problema?” a spus Béla Bollobás, care a fost consilierul doctoral al lui Morris și Sahasrabudhe la Universitatea din Memphis. „De atunci, s-a dovedit că este o problemă foarte mare, pentru că de-a lungul anilor au fost scrise câteva mii de lucrări despre diferite variante ale problemei Ramsey.” La fel de Liana Yepremyan, un matematician la Universitatea Emory, a spus: „Numerele Ramsey creează acea punte între combinatorie și probabilitate și geometrie”.

Teoria jocului

 În august 2018, Sahasrabudhe a fost bursier postdoctoral sub Morris la IMPA. Cei doi sperau să înceapă un nou proiect cu Griffiths, care predă la Universitatea Pontificală Catolică din apropiere, când o lucrare de Conlon le-a atras atenția. Lucrarea a subliniat o posibilă strategie pentru obținerea unei îmbunătățiri exponențiale a numărului Ramsey. Griffiths, Morris și Sahasrabudhe au început să se joace cu ideea.

„A fost foarte interesant la început”, și-a amintit Sahasrabudhe. Le-a luat doar o lună, a spus el, pentru a prezenta o schiță a argumentului lor.

Planul lor a fost să se bazeze pe ideile folosite în dovada originală a lui Erdős și Szekeres că $latex R(k) < 4^k$. Pentru a demonstra că numărul Ramsey este de cel mult $latex 4^k$, imaginați-vă că jucați un joc pe un grafic complet cu $latex 4^k$ noduri. Jocul are doi jucători. În primul rând, adversarul tău colorează fiecare margine fie roșu, fie albastru, sperând să coloreze marginile într-un mod care să evite crearea unei clicuri monocromatice de k noduri.

Odată ce adversarul tău a terminat de colorat, este treaba ta să cauți o clică monocromatică. Dacă găsești unul, câștigi.

Pentru a câștiga acest joc, poți urma o strategie simplă. Vă ajută să vă gândiți (metaforic) la sortarea nodurilor în două găleți. Nodurile dintr-o găleată vor forma o clică albastră, iar nodurile din cealaltă vor forma o clică roșie. Unele noduri vor fi șterse și nu vor mai fi auzite niciodată. La început, ambele găleți sunt goale și fiecare nod este un candidat pentru a intra în oricare dintre ele.

Începeți cu orice nod care vă convine. Apoi uitați-vă la marginile de legătură. Dacă jumătate sau mai multe dintre margini sunt roșii, atunci ștergeți toate marginile albastre și nodurile la care sunt conectate. Apoi puneți alegerea inițială în găleata „roșie”. Toate marginile roșii ale acestui nod sunt încă vii și bine, agățate de restul graficului din interiorul găleții. Dacă mai mult de jumătate dintre margini sunt albastre, ștergeți în mod analog marginile și nodurile roșii și le puneți în găleată albastră.

Repetați până când nu mai aveți noduri. (Deoarece graficul este complet, fiecare nod rămas în orice punct este conectat la ambele găleți până când este plasat într-una dintre ele.)

Când ați terminat, uitați-vă în interiorul găleților. Deoarece un nod a intrat în găleată roșie numai după ce vecinii săi albaștri au fost eliminați, toate nodurile din găleată roșie sunt conectate prin margini roșii - formează o clică roșie. La fel, găleata albastră formează o clică albastră. Dacă graficul dumneavoastră original are cel puțin $latex 4^k$ noduri, este posibil să demonstrați că una dintre aceste găleți trebuie să conțină cel puțin k noduri, garantând o clică monocromatică în graficul original.

Acest argument este inteligent și elegant, dar te face să construiești două clicuri - una albastră și una roșie - chiar dacă ai nevoie doar de una. Ar fi mai eficient să devină mereu roșu, a explicat Conlon. În cadrul acestei strategii, ai alege un nod la fiecare pas, ai șterge marginile albastre și l-ai arunca în găleată roșie. Găleata roșie se umplea rapid și ai aduna o clică roșie de k noduri în jumătate din timp.

Dar strategia ta trebuie să funcționeze pentru orice colorare roșu-albastru și este greu de știut dacă poți găsi întotdeauna un nod cu multe margini roșii. Așa că, în urma sugestiei lui Conlon, există riscul de a alerga într-un nod care aproape că nu are margini roșii atașate. Asta te-ar forța să ștergi o porțiune uriașă a graficului dintr-o dată, lăsându-te să te străduiești să-ți construiești clica înainte de a rămâne fără noduri. Pentru a duce la bun sfârșit sugestia lui Conlon, Griffiths, Morris și Sahasrabudhe trebuiau să demonstreze că acest risc era evitabil.

Un examen cu carte deschisă

În actualizarea gameplay-ului, Griffiths, Morris și Sahasrabudhe au urmat un traseu puțin mai ocolit. În loc să construiască o clică monocromatică direct, aruncând noduri în gălețile lor roșii și albastre, ei s-au concentrat mai întâi pe construirea unei structuri numită carte roșie.

O carte, în teoria grafurilor, este alcătuită din două părți: există o clică monocromatică, numită „coloana vertebrală” și un al doilea grup distinct de noduri numite „pagini”. Într-o carte roșie, toate marginile care leagă nodurile din cotorul sunt roșii, la fel ca și marginile care leagă cotorul de pagini. Cu toate acestea, marginile care conectează nodurile din pagini pot fi orice combinație de culori. Conlon a notat în lucrarea sa din 2018 că, dacă poți găsi o clică roșie în paginile unei cărți, atunci ai putea să o combinați cu cotorul pentru a obține o clică roșie mai mare. Acest lucru vă permite să descompuneți o căutare pentru o clică roșie mare în două căutări mai ușoare. În primul rând, caută o carte roșie. Atunci caută o clică în paginile cărții.

Griffiths, Morris și Sahasrabudhe au vrut să ajusteze algoritmul câștigător al jocului, astfel încât să construiască o carte roșie în loc de o clică roșie. Deși s-au hotărât pe acest plan la doar câteva săptămâni de la începutul proiectului lor, ar dura ani pentru ca acesta să funcționeze. Mai aveau nevoie să evite amenințarea de a-și pierde toate marginile roșii.

„Am fost blocați foarte mult timp”, a spus Campos, care s-a alăturat proiectului în 2021.

În ianuarie, cei patru matematicieni au convenit să treacă la o altă versiune a problemei. Versiunea respectivă sună mai complicată, dar s-a dovedit a fi mai ușoară.

Tot timpul, echipa a fost concentrată pe numărul Ramsey R(k), cunoscut și sub numele de numărul Ramsey „diagonal”. Un grafic de dimensiunea R(k) trebuie sa contina k noduri, toate conectate prin margini de aceeași culoare, dar nu contează dacă acea culoare este roșie sau albastră. Pe de altă parte, numărul Ramsey „în afara diagonalei” R(k, l) măsoară cât de mare trebuie să fie un grafic înainte de a conține fie o clică roșie cu k noduri, sau o clică albastră cu l noduri. În loc să continue să pirateze problema diagonalei, grupul a decis să încerce versiunea off-diagonală. Acest lucru sa dovedit revelator.

„Pentru o lungă perioadă de timp, am simțit că fiecare ușă pe care ați împins a fost fie închisă cu șuruburi, fie cel puțin destul de greu de trecut”, a spus Griffiths. „Și după acea schimbare, simțeai că fiecare ușă era deschisă. Cumva, totul părea să funcționeze.” În versiunea off-diagonală, au găsit o modalitate de a șterge o grămadă de margini albastre dintr-o dată, urmând un anumit protocol, care a crescut densitatea marginilor roșii și a dus la o limită îmbunătățită a numărului Ramsey în afara diagonalei. Această metodă, numită argument „increment de densitate”, a fost folosită anterior pentru a rezolva alte probleme importante din combinatorică, dar nu fusese folosit în problema numărului Ramsey.

Cei patru matematicieni au folosit apoi noua limită a numărului Ramsey în afara diagonalei pentru a deschide calea pentru rezultatul diagonală. Până la începutul lunii februarie, ei au scăzut în sfârșit limita numărului Ramsey cu un factor exponențial, o realizare pe care matematicienii au căutat-o ​​timp de aproape un secol. Și au făcut-o modernizând aceeași linie de argumentare pe care Erdős și Szekeres au prezentat-o ​​în 1935.

Epsilon, Epsilon

După discuțiile din 16 martie, participanții au început să confirme zvonurile. Fotografiile din discursul lui Sahasrabudhe au circulat prin apeluri telefonice și mesaje private - chiar și într-un post vag, dar sugestiv pe blogul matematicianului Gil Kalai. Campos, Griffiths, Sahasrabudhe și Morris au susținut că au arătat că $latex R(k) < 3.993^k$. În acea noapte, cei patru autori și-au postat lucrarea online, permițând matematicienilor să vadă singuri noua dovadă.

„Cred că mulți dintre noi nu ne așteptam să vedem o astfel de îmbunătățire în viața noastră, în esență”, a spus Matija Bucić, matematician la Universitatea Princeton și la Institutul pentru Studii Avansate. „Cred că este un rezultat absolut uimitor.”

Mulți experți speră că, odată cu doborârea barierei exponențiale, vor urma rapid mai multe progrese. Autorii noii lucrări nu și-au împins în mod intenționat metoda la limite, pentru a evita întunecarea argumentului lor cu detalii inutile. „Sunt foarte interesat de cât de departe poate merge metoda, pentru că habar n-am”, a spus Campos.

„Este o dovadă absolut ingenioasă, absolut minunată și o descoperire reală. Așa că acum mă aștept ca porțile să fie deschise”, a spus Bollobás. „Sunt convins că peste trei ani, dezbaterea va fi despre posibile îmbunătățiri. Putem îmbunătăți 3.993 la 3.9? Poate la 3.4? Și ce zici de 3?”

Noua dovadă vine la 56 de pagini și va dura săptămâni pentru ca fiecare detaliu să fie pe deplin verificat de comunitatea de combinatorie. Dar colegii sunt optimiști. „Acest grup de autori, sunt oameni foarte serioși. Și sunt oameni care sunt foarte, foarte buni la lucruri foarte tehnice”, a spus Wigderson.

Când vine vorba de colaboratorii săi, Griffiths este de acord. „Este un privilegiu să lucrezi cu oameni străluciți, nu-i așa? Și cred că pentru asta sunt foarte recunoscător”, a spus el. „Dacă mi-ar fi lăsat-o pe seama mea, poate mi-ar fi trebuit încă cinci ani să înțeleg detaliile corect.”