A matematikusok új módszert fedeztek fel a grafikonok szerkezetének előrejelzésére | Quanta Magazin

Izgalmas év volt ez a kombinatorikai kutatásban. 2023 elején a matematikusok megdöbbentek, amikor kettő a legnagyobb problémák a terepen annyi hónap alatt megoldódott. Most egy harmadik nagy kérdés esett egy 14 oldalas bizonyítással, „amelynek teljesen megfelelő ötletei vannak” – mondta. Mehtaab Sawhney a Massachusetts Institute of Technology munkatársa, aki hozzátette: „Teljesen megdöbbentő.”

Ez a kérdés az úgynevezett Ramsey-számokkal foglalkozik – alapvető mennyiségekkel, amelyek a lehetséges zavar határait tükrözik. Ezek a számok azt a méretet mérik, amelyet a csúcsok és élek gyűjteményei, úgynevezett gráfok elérhetnek, mielőtt elkerülhetetlenül mintázatot és szerkezetet hoznának létre.

A matematikusok közel egy évszázada tanulmányozzák a Ramsey-számokat, amelyeket köztudottan nehéz meghatározni. Ennek során olyan technikákat fejlesztettek ki, amelyek a gráfelméleten túl számos tudományágban is előrelépéshez vezettek, beleértve a számelméletet és a kriptográfiát is.

De az új bizonyíték, a hónap elején tette közzé az interneten, eltérést jelent azoktól a technikáktól. Nemcsak egy olyan problémát old meg, amely több mint 40 éve ellenállt a fejlődésnek, hanem egy újszerű ütemtervet is bemutat arra vonatkozóan, hogy a matematikusok hogyan kezelhetik a Ramsey-problémákat a jövőben.

A partitervezés találkozik a gráfelmélettel

Ahhoz, hogy megértse, mi az a Ramsey-szám, képzelje el, hogy partit rendez.

Hány embert kellene meghívnia annak biztosításához, hogy legyen egy olyan embercsoport, akik mind ismerik egymást, vagy egy csoport, akik mind idegenek? Ezt a kérdést a gráfok nyelvén kódolhatja. Minden személyhez rendeljen egy csúcsot. Mert n emberek, érted n csúcsok. Köss össze minden csúcspárt éllel. Színezd ki a szélét pirosra, ha a szóban forgó személyek ismerik egymást, és kékre, ha idegenek.

A közös ismerősök vagy idegenek csoportját egy klikknek nevezett szerkezet képviseli: azonos színű élekkel összekapcsolt csúcsok halmaza. A Ramsey-szám r(s, t) a minimális számú embert, akit meg kell hívnia, hogy lehetetlenné tegye egy csoport bevonását s ismerősök ill t idegenek – a gráfelmélet nyelvén a méret vörös klikkje s vagy egy nagyságú kék klikk t.

Például tudjuk, hogy r(4, 5) = 25. Tehát 24 fős bulit rendezhet, akik közül néhányan ismerik egymást anélkül, hogy négy közös ismerősből vagy öt idegenből álló csoportot vennének magukkal. De adjon hozzá még egy személyt, és nem kerülheti el, hogy létrehozzon legalább egy ilyen struktúrát.

A kombinatorika idei egyik korábbi áttörése szigorúbb felső korlátot adott a „szimmetrikus” Ramsey-számoknak, ahol a piros és kék klikkek azonos méretűek. Aszimmetrikus Ramsey-számokkal – az új eredmény tárgyával – a matematikusok rögzítik a vörös klikk méretét, és megkérdezik, mi történik, ha a kék klikk mérete tetszőlegesen megnő.

A matematikusok csak a legkisebb Ramsey-számok egy maroknyi számát tudták pontosan kiszámítani. Ezt bebizonyították r(4, 5) = 25 1995-ben. De senki sem tudja ennek értékét r(4, 6). Hasonlóképpen az 1980-as évek elején mutatták meg hogy r(3, 9) = 36, de r(3, 10) továbbra is nyitott probléma. (A szimmetrikus eset ugyanolyan nehéz: r(4) = 18, de az értéke r(5) nem ismert.)

Ezért a matematikusok ehelyett megpróbálják megbecsülni a Ramsey-számokat – értékük felső és alsó határát hozva létre.

Az 1990-es években véletlenszerűen generált grafikonokat alkalmaztak annak bizonyítására, hogy ha a piros klikket 3-ban rögzítették, a kék pedig egyre nagyobb lesz, akkor a Ramsey-szám mérete a kék klikk méretének négyzetével nő. Más szavakkal, r(3, t) megközelítőleg t².

Az új bizonyíték azt kérdezi, hogy mi történik, ha a vörös klikk méretét 4 helyett 3-ra állítják. Az 1930-as években megállapították, hogy r(4, t) nem nő gyorsabban, mint kb t³. De az 1970-es években talált legjobb alsó határ kb t^5/2 - lényegesen kisebb.

Azok az erőfeszítések, amelyek az alsó határ megemelésével vagy a felső csökkentésével megszüntették a különbséget, évtizedekig kudarcot vallottak, mígnem egy matematikuspár hozzáadott egy kulcsfontosságú összetevőt.

Rejtett látványban

A 2019, Sam Mattheus, akkor a Brüsszeli Szabadegyetem (VUB) végzős hallgatója keresett ihletet. Szakértelmét a véges geometria, a pontok, vonalak és egyéb szerkezetek speciálisan meghatározott terekben történő elrendezésének tanulmányozása képezte. De annak ellenére, hogy érdekesnek találta a munkát, úgy érezte, korlátozza, mennyire szigorúnak és pontosnak kell lenniük ezeknek a geometriai konstrukcióknak.

Aztán látta egy papír két matematikustól, Dhruv Mubayi az Illinoisi Egyetemen, Chicagóban és Jacques Verstraete a San Diego-i Kaliforniai Egyetemen. Újragondolták, hogyan közelítsék meg Ramsey problémáit. Míg a hagyományos technikák véletlenszerűen generálják a grafikonokat, hogy jó becsléseket kapjanak a Ramsey-számokról, addig Mubayi és Verstraete „álvéletlen” konstrukciókkal kezdte, amelyek véletlenszerűnek tűnnek, de nem azok.

Valami kattant Mattheusban. Talán, gondolta, a geometriai perspektívája segíthet. A következő néhány évben, amíg befejezte a diplomamunkáját, ezt az ötletet a fejében tartotta. Ezután jelentkezett egy Fulbright-ösztöndíjra, amely lehetővé tenné számára, hogy posztdoktori tanulmányokat folytasson Verstraete-nél az Egyesült Államokban.

2022-ben, nem sokkal azután, hogy Mattheus megkapta a Fulbright-díjat (együtt egy másik közösség), az UCSD-hez költözött, és a Verstraetével kezdett dolgozni r(4,t). A matematikusok meg akarták emelni az alsó korlátot, hogy megfeleljen az ismert felső határnak. Ehhez egy grafikont kellene találniuk a közel t³ olyan csúcsok, amelyekben nem voltak 4-es méretű vörös vagy kék klikkek t.

Ahhoz, hogy a bizonyítékuk működjön, újrafogalmazták a problémát. Képzelje el, hogy egyszerűen töröl minden kék élt. A cél most egy olyan grafikon megtalálása, amelyen nincsenek 4-es méretű vörös klikkek és nincsenek független méretű halmazok. t (vagyis készletei t csúcsok élek nélkül).

Mubayi és Verstraete 2019-es munkája arra utalt, hogy ha meg tud konstruálni egy pszeudovéletlen gráfot 4-es méretű vörös klikkek nélkül, akkor abból véletlenszerű darabokat vesz, hogy kisebb gráfokat kapjon nagy független halmazok nélkül. Mattheus és Verstraete pontosan ezt akarta megtalálni. Egy még nagyobb grafikonnal kezdve azt remélték, hogy találnak egy olyan grafikont, amelyen majdnem t³ a kritériumoknak megfelelő csúcsokat. „Ezek a grafikonok jobb Ramsey-gráfokat rejtenek” – mondta Verstraete.

A probléma az volt, hogy kitaláljuk a megfelelő pszeudovéletlen konstrukciót.

A matematikusoknak némileg körbe kellett jutniuk. Nem pszeudovéletlen grafikonnal kezdték. Egyáltalán nem grafikonnal kezdték.

Ehelyett Mattheusnak eszébe jutott egy furcsa objektum, amelyet hermitiánus egységnek neveznek, amit a véges geometriák általában nagyon jól ismernek – de amivel a kombinatorikával dolgozó matematikus nem valószínű, hogy valaha is találkozna.

A hermitiánus egység a görbén lévő pontok speciális halmaza, olyan vonalakkal együtt, amelyek meghatározott konfigurációkban haladnak át ezeken a pontokon. Lényeges, hogy egy gráfként is ábrázolható, amely sok nagy, de alig átfedő klikkből áll.

Ez a grafikon jól ismert, és számos tulajdonságát tanulmányozták. De ezt soha nem vették figyelembe a Ramsey-problémák összefüggésében. „Ez nagyon jellemző erre a véges geometriával foglalkozó üzletágra” – mondta Mattheus.

A grafikon első pillantásra talán nem tűnik hasznosnak, mivel olyan sok nagy klikket tartalmaz. De a Hermitian unitál egyik legfontosabb jellemzője, hogy csak 4-es méretű klikkeket tartalmaz, amelyek csúcsai atipikus módon csoportosulnak egymáshoz. Ennek a tulajdonságnak köszönhetően a matematikusok viszonylag könnyen elpusztíthatták ezeket a nem kívánt klikkeket az élek véletlenszerű törlésével.

Ezek a törlések egy új gráfot adtak nekik 4-es méretű klikkek nélkül – de még mindig nagy független halmazokat tartalmazott. Mattheusnak és Verstraetének most be kellett bizonyítania, hogy ez a gráf álvéletlen. Ennek során végre a 2019-es bizonyítást remélték. Véletlenszerű részgráfokat vettek fel kb t³ csúcsokat, és garantálni tudta, hogy ezek a részgráfok mentesek a független mérethalmazoktól t.

Ezzel befejeződött a bizonyítás. "Ez az építmény teljesen gyönyörű" - mondta Sawhney.

A munka egy változást hirdet a matematikusok Ramsey-problémákról való gondolkodásában. „Nagyon-nagyon természetes, hogy megpróbáljuk a véletlenszerűséget felhasználni, hogy megpróbáljuk átnyomni a dolgokat, és a lehető legjobb korlátokat betartani” – mondta. David Conlon a California Institute of Technology munkatársa. "De ez valójában azt mutatja, hogy a véletlenszerűség csak idáig visz."