Simonyi Gábor 2025 április 25-én hunyt el Budapesten. Pár hónapja töltötte be 63. életévét, de sokkal fiatalabbnak tűnt. Fiatalságra mutató koromfekete haja, mosolya, kifogyhatatlan energiája és ötletgazdagsága bátorították a diákokat, akik feltűnően nagy számban váltak tanítványaivá, ahol csak tanított, a Budapesti Műszaki Egyetem matematikus szakán vagy az angol nyelvű Budapest Semesters in Mathematics gráfelmélet kurzusán. Gábor egyetemi tanár volt a BME-n, az MTA matematikus doktora és kutatóprofesszor a Rényi Intézetben.
18 évesen maximális pontszámmal szerzett abszolút elsőséget és ezzel aranyérmet a Nemzetközi Matematikai Diákolimpián Washingtonban. Mégis, a matematika önzetlen szerelmeseként akkor még úgy érezte, a tehetsége nem egyértelműen elég a matematikus karrierhez, így a Budapesti Műszaki Egyetem Villamosmérnöki Karán szerzett mérnöki diplomát 1986-ban. Diákévei alatt mindvégig szoros baráti kapcsolatban maradt diákolimpikon versenytársaival, és végzése után az információelmélet hídján keresztül azonnal visszatért a matematikához, amikoris aspiráns lett az MTA Matematikai Kutató Intézetében.
Az információelmélet a hírközlés matematikája, telisteli elemien megfogalmazható, de sokszor mindmáig megoldatlan kombinatorikai problémákkal. Ezek közül 70 év óta kimagaslik egy, ami a zajos hírcsatornákon való hibátlan, úgynevezett zéró hibájú hírátvitelre vonatkozik. Ennek lehetőségét Claude E. Shannon amerikai mérnök-matematikus vette észre. A Shannon által gráfelméleti nyelvre átfogalmazott jelenség pontos matematikai természete még ma is ismeretlen. A Shannon által nyitva hagyott legegyszerűbb speciális eset az úgynevezett öt hosszú kör gráf kérdése, amelyet 23 év intenzív nemzetközi próbálkozásai után Lovász László fejtett meg, de minden ennél hosszabb, páratlan pontszámú körre a kérdés ma is megoldatlan. Mi értelme, haszna lehet mégis a Shannon-probléma messzemenő általánosításainak, és milyen elmélet kerekedhet belőlük? Ezt a kérdést járja körül és válaszolja meg rendkívül meggyőzően Simonyi Gábor torzójában is sikeres életműve.
Shannon problémájában a zajos csatornát egy véges gráf testesíti meg. A gráf szögpontjai felelnek meg azoknak a jeleknek, amelyek révén kommunikálhatunk a csatornán. Minden jel leadásakor a csatorna másik végén, a kimeneten egy másik, általában különböző jel jelenik meg. A leadott és a kimeneten látható jel kapcsolata véletlen, másnéven sztochasztikus jellegű. Ha azonban a különböző bemeneti jelek esetén lehetséges kimeneti jelek halmaza nem mindig azonos, akkor a megfelelő csatornát használva lehetséges a hibátlan kommunikáció. Pontosabban, ez akkor lehetséges, ha van legalább két olyan bemeneti jel, amelyekre a lehetséges kimeneti jelek halmaza diszjunkt, vagyis nincs közös eleme. Két ilyen bemeneti jelet megkülönböztethetőnek nevezünk. Ezt a helyzetet írja le Shannon a csatornához rendelt gráffal. A gráf két pontját akkor kötjük össze éllel, ha a megfelelő két jel megkülönböztethető. A kommunikáció során egymás után, sorozatban adjuk le a jeleket. Két jelsorozat pontosan akkor megkülönböztethető, ha bennük valahol, ugyanabban a pozícióban megkülönböztethető jelek állnak. Ha a gráfunk \(G\), legyen az \(n\) hosszúságú, páronként megkülönböztethető jelsorozatok maximális száma \(C(G,n)\). Rögzített gráfra a \(C(G,n)\) számsorozat \(n\)-nel exponenciálisan növekszik. Az exponens aszimptotikus értékét nevezik a gráf kapacitásának. Ha az \(L\) gráfnak két pontja van, és ezek megkülönböztethetőek, akkor \[C(L,n)=2^n.\] A helyzet ugyanez bármilyen egyetlen éllel rendelkező \(E\) gráfra, azaz itt is \[C(E,n)=2^n.\] Nevezzük a leadható sorozatok halmazát kódnak. Értelemszerűen a kódot a csatorna ismeretében választjuk meg, vagyis tudván, hogy mely jelpárok megkülönböztethetőek. De mi van akkor, ha a kódot úgy kell megtalálni, hogy a csatornát nem ismerjük, csak annyit tudunk róla, hogy az egy véges halmaz valamelyik eleme, azaz egy adott \(\mathsf{L}\) gráfcsalád tagja? Próbáljuk meghatározni \(C(\mathsf{L},n)\)-t, azaz az \(\mathsf{L}\) minden csatornájára jó, \(n\) hosszúságú sorozatokból álló kód maximális méretét. Mi értelme lehet, hogy ily módon megnehezítve tegyük fel az amúgyis megoldatlan problémát? Az erre adott választ Rényi Alfréd egy akkor már legalább harminc éve nyitott és intenzíven kutatott problémájában találtuk meg Simonyi Gáborral. A Rényi-probléma megoldásához ugyanis éppen egy speciális, egyszerű gráfcsaládra kellett megoldani a mi kódolási problémánkat. Rényi azt kérdezte, hányféleképpen lehet \(k\) részre partícionálni, (azaz feldarabolni) egy \(n\) elemű halmazt úgy, hogy bármely két partíció bármely két osztálya messe egymást? Legyen az ilyen partíciók maximális száma \(R(k,n)\). Mármost, ha tekintjük azon \(\mathsf{L}_k\) gráfcsaládot, amelynek gráfjai mind egyélűek, és ezek az élek rögzített \(k\) pont között feszülnek, akkor könnyű látni, hogy erre a gráfcsaládra \(C({\mathsf{L}}_k,n)=R(k,n-k)\). Mikor Gábor és én kezünkbe vettük a gráfcsaládok kérdését, még \(k=3\)-ra sem volt ismert \(C({\mathsf{L}}_3,n)\) értéke. Annyit lehetett csak tudni, hogy ennek az értéknek az exponenciális nagyságrendje \(2^{n/3}\) és \(2^{2n/3}\) között van. Mi azonban beláttuk, hogy az alsó korlát nagyságrendje jóval nagyobb, azaz az aszimptotikus exponens nagyobb, mint 1/3. Ez utat nyitott pár évvel később a kérdés minden \(k\)-ra való teljes megoldására. Mint ezen megoldás egyik szerzője, biztonsággal állíthatom, hogy Gábor korábbi ötletei nélkül nem született volna meg ez a megoldás. Döntő szerepet játszott itt az a felismerés, hogy Rényi partíciókra vonatkozó kérdése a gráfkapacitás kérdéskörének integráns része.
A közös problémáinkhoz és így a barátságunkhoz való hűség meg a tudományos kíváncsiság tette, hogy Gábor számos cikke foglalkozik a gráfkapacitás kérdésének irányított gráfokra és azok családjaira való általánosításával, még végtelen gráfok családjaira is. Ezen cikkek társszerzőinek hosszú sorában kiemelkedő szerepet játszanak Gábor doktorandusz diákjai épp úgy, mint világhírű matematikusok, például Noga Alon, Ron Holzman, Bojan Mohar vagy Tardos Gábor. Mi ketten 15 közös cikket írtunk, eleinte Budapesten, később levelekben, vagy együtt járva a világot. A Rényi-probléma fent vázolt megoldása Párizsban „fogant”, ahol Gábor a fülem hallatára tanult meg fél év alatt franciául, de arra is maradt ideje, hogy frissen végzett egyetemistaként beiratkozzon és engem is elcsábítson a minket vendégül látó egyetem ivrit, azaz modern héber nyelvtanfolyamára. Két évvel később Avi Wigderson meghívását élvezve együtt bukdácsoltunk Izraelben a Negev sivatagban és a gráfentrópia matematikájában. Avi meghívását annak köszönhettük, hogy Gábor egy nagyszerű áttekintő cikkével széles körben megismertette a gráfentrópiát, ezt az információelméleti fogalmat, amellyel korábban (részben társszerzőkkel) sikeresen jellemeztük és általánosítottuk a perfekt gráfok fogalmát. De jártunk együtt a Cornell Egyetemen és a Comói-tónál vagy Rómában, ahol utoljára volt időnk hónapokig együtt gondolkozni. Gábor ilyenkor sosem félt kísérletezni a mindenkori helyi nyelv tanulásával.
Írtam, hogy egyetlen véges gráf kapacitásáról ma is nagyon keveset tudni, akár egészen egyszerű gráfokra is. Egyre absztraktabb és mélyebb eszközöket vet be a kutatás ebben a témában. Utolsó cikkei egyikében Gábor nagy figyelmet keltő eredményeket publikált Shannon ezen alapkérdéséről is. Felfedezései velünk maradnak, de bátorító mosolyától, új, gondolatébresztő ötleteitől, varázsos egyéniségétől mindörökre el kellett búcsúznunk áprilisban.
Körner János
egyetemi tanár, Sapienza Universitá di Roma
