2020. dec 06.

Matematikus hallgató kitolja a gráfelmélet határait

írta: Janguli
Matematikus hallgató kitolja a gráfelmélet határait

Erdős Pál és Szekeres György nyomában

Ashwin Sah (MIT) 21 éves korára olyan teljesítményt tett le az asztalra, amely vezető matematikusok szerint szinte példa nélküli egy egyetemi hallgató esetén, s már most elegendő lenne ahhoz, hogy kari pozíciót szerezzen.

Az AmberGlen parkban, közel szülővárosához, Portland-hez (Oregon)

Május 19-én Ashwin Sah a kombinatorika egyik legfontosabb kérdésével kapcsolatban az eddigi legjobb eredményt tette közzé. Ilyen pillanathoz ünnepi ital dukál, csakhogy Sah még nem volt elég idős ahhoz, hogy rendelhessen egyet.

Sah, aki novemberben töltötte be a 21. évét, a MIT hallgatójaként már e bizonyítás előtt is egy sor matematikai eredményt publikált. Ritka koraérettség ez még egy ilyen területen is, amelyre általában véve jellemző a zsenialitás fiatal kori megjelenése.

A májusi bizonyítás a kombinatorikában fontos szerepet betöltő ún. Ramsey-számokra összpontosít (névadójuk a szintén koraérett, és sajnos korán elhunyt Frank P. Ramsey brit matematikus, filozófus, közgazdász). Ezek azt számszerűsítik, hogy mekkora lehet egy gráf az előtt, hogy szükségszerűen tartalmazna egy bizonyos fajta alstruktúrát.

ramsey.jpgFrank Plumpton Ramsey (1903-1930)

Képzeljük el például, hogy adott hat csúcs, és mindegyiket élek kötik össze minden más csúccsal. Most színezzük ki mind a 15 élt vörösre vagy kékre. Nem számít, hogyan alkalmazzuk a színeket, elkerülhetetlenül eljutunk oda, hogy három csúcsot azonos színű élek kössenek össze egymással (ezt nevezik „klikknek”). Ugyanez nem igaz, ha öt csúccsal kezdünk: így a színezés klikk létrehozása nélkül is elvégezhető. Így a matematikusok azt mondják, hogy a Ramsey-szám két szín és 3-as méretű klikk esetén 6 – vagyis legalább hat csúcs kell ahhoz, hogy a klikk garantáltan létrejöjjön.

Ahogy a keresett klikk mérete nő, egyre nehezebb kiszámítani a pontos Ramsey-számokat. Ehelyett a matematikusok megpróbálják úgy eltalálni őket, hogy garantálják: a Ramsey-szám adott méretű klikk esetében nagyobb, mint egy adott szám (az „alsó határ”), és kisebb, mint egy másik (a „felső határ”).

Erdős Pál és Szekeres György a harmincas években kezdeményezte a Ramsey-számok felső és alsó határának tanulmányozását. Azóta a matematikusok mind a felső, mind az alsó határt illetően viszonylag kevés előrehaladást értek el – ámbár a Quanta nemrégiben bemutatott egy új, innovatív bizonyítást, amely egyes Ramsey-számokra a valaha volt legjobb alsó határt adta meg.

Balra Szekeres György, középen Klein Eszter (Szekeres György felesége), jobbra Erdős Pál 

Ashwin Sah bizonyítása ezzel szemben a kétszínű Ramsey-számok felső határának pontosságát javította. Ezt úgy érte el, hogy optimalizálta az Erdőstől és Szekerestől eredő, néhány matematikus által továbbfejlesztett módszert. Sah eredménye azt bizonyítja, hogy ha a gráf elér egy bizonyos méretet, akkor elkerülhetetlenül tartalmaz valamilyen megfelelő méretű klikket. A szakterületen sokan Sah bizonyítását tartják a legjobb eredménynek, amely e kutatásban egyáltalán elérhető.

„Eljut a módszer logikai határáig" – mondja David Conlon, a Kaliforniai Műszaki Intézet munkatársa, aki az előző legjobb felső határt adta meg a problémára.

Egy élet a matekért

Sah az oregoni Portland-ben nőtt fel, és már fiatal korától kedvelte a matematikát. „Néhány legkorábbi emlékem azzal kapcsolatos, hogy anyám a számtani alapokra tanít" – mondta.

Haladó matematikából a versenyeken kapott első ízelítőt, ahol remekelt. 2016 nyarán, 16 éves korában aranyérmet nyert a hongkongi nemzetközi matematikai olimpián. A következő évben beiratkozott az MIT-re, majd két és fél év alatt végzett.

Az MIT-n Sah két, a matematikai fejlődésében kulcsfontosságú szerepet játszó kapcsolatot létesített. Az elsőt Yufei Zhao nevű professzorával. Sah az MIT-ben töltött első éve alatt két osztályt végzett el nála, köztük egy diplomás szintű kombinatorika-szemináriumot. Sah még a világ legtehetségesebb matematikus hallgatói közül is kiemelkedett.

Yufei Zhao

Sah 11 éves korában

A másik kapcsolat Mehtaab Sawhney-val létesült, aki most 22 éves. Sawhney egy évvel megelőzte Sah-t, és azon az őszön került át a Pennsylvaniai Egyetemről az MIT-re. Szeptemberben találkoztak az évfolyamon, és barátságot kötöttek.

Tavaszig kutatták együtt a diszkrét matematika számos témáját, úgymint a gráfelmélet, a valószínűség és a random mátrixok tulajdonságai. Az általuk tárgyalt problémák közül sok viszonylag egyszerűen megfogalmazható volt, és anélkül is meg tudták közelíteni őket, hogy szükségük lett volna az évekig tartó formális képzésre, amellyel még nem rendelkeztek.

„Azokat a problémákat szeretem, amelyekről az alapelvekből kiindulva gondolkozhatsz, és nem kell hatalmas mennyiségű irodalmat olvasnod, vagy rengeteg elméletet tudnod ahhoz, hogy eltöprengj rajtuk” – mondta Sawhney.

Szorosan együttműködtek Zhaóval, aki kérdéseket javasolt kutatásukhoz, és megtanította őket arra, hogyan kell hivatalos matematikai dolgozatokat írni. Zhao gyakran kérte őket egy-egy probléma vizsgálatára, hátha az egy ideig lefoglalja őket, de már másnap a válasszal tértek vissza: „Mindketten hihetetlenül energikus egyének. Felvetek egy kérdést, és szinte azonnal hallom a választ”.

Az elmúlt három évben Sah és Sawhney tucatnyi tanulmányt írt, sokat együtt. Idén ősszel kihirdették, hogy ők a 2021-es Morgan-díj nyertesei, amelyet a vezető matematikai szervezetek minden évben közösen osztanak ki az egyetemi hallgató matematikusok legjobb kutatásainak elismeréséül. Zhao szerint a közelmúltban nincs precedens arra, amit elértek: „Régi hagyományai vannak az egyetemi hallgatók kutatásainak, de mennyiségben és minőségben messze nem Ashwin és Mehtaab szintjén”.

Sah és Sawhney a MIT hallgatói, bár a járvány miatt jelenleg egymással szemközti parton tartózkodnak. Sah visszatért Portlandbe, Sawhney pedig a New York-i Long Islandre, ahol felnőtt. De továbbra is szinte szüntelen kapcsolatban állnak egymással.

Azt mondják, korai sikerük nem nyomasztja őket. Ha valamire, akkor arra ösztönzi őket, hogy meghaladják. „Megpróbálok nem a múltra koncentrálni – mondja Sah. – Mindig előre nézek, hogy mivel foglalkozhatok a következőkben.”

Forrás: Kevin Hartnett, Quanta

Szólj hozzá

tudomány erdős pál gráfelmélet gráfok erdős pál matematikus