A hidak építése: Lovász László születésnapi konferenciája

1. Konferenciák és a magyar matematikai élet

Amikor egy ilyen cikk írásába kezdünk, érdemes előbb elgondolkodnunk azon, hogy kik számára írjuk. Ez a cikk olyan olvasók számára íródott, akik vagy matematikatanárok, vagy matematikusok, vagy az átlagosnál jobban érdeklődnek a matematika, a matematikusok, és a matematikai élet iránt. A cikkben van egy kis matematika is, de nem sok, és ahol matematikáról írok, ott mindenütt megpróbáltam elkerülni a technikai részleteket.

Maga a cikk három részre bomlik. Az első részben a magyar matematikai élet bizonyos vonásairól írok, a másodikban a Lovász-konferenciáról. A harmadik részben írok Lovász Lászlónak a matematikai életünkben betöltött szerepéről, és a matematikájáról.

– –

Régi hagyomány hazánkban, hogy legjobbjaink kerek születésnapjain nemzetközi konferenciákat szervezünk. Volt egy ehhez kapcsolódó másik hagyomány is, amelyben évfordulókon egymás matematikájáról irtak barátok, kollegák, elsősorban a Matematikai Lapokban. Még ma is élvezettel olvasom Turán Pál azon cikkét, amelyet „Erdős Pál 50 éves” cimmel írt. A későbbiekben sokan írtak cikkeket Erdős Pál születésnapjai vagy mások születésnapjai alkalmából...

Lovász Laci idén lett 70 éves. Ebből az alkalomból a környezete egy nagyobb méretű matematikai konferenciát szervezett. Maga a konferencia sok szempontból hasonlított Laci 60. születésnapjára szervezett konferenciára, amelynek neve „Building Bridges”, azaz „Hidak építése” volt. Ezután nem olyan nagyon meglepő, ha az idei konferencia elnevezése „Building Bridges II” volt. A „Building Bridges” jelentése itt az, hogy Lovász egy hídépítő, de nem a Duna két partja, hanem a matematika egymástól távolabb eső területei közé építi a hídjait.

Manapság persze nagyon divatos „hidak” az „interdiszciplináris” tudományok, ezek közül legelőször talán a matematikai fizikával találkoztunk, majd a fizikai kémiával, de azóta nagyon sok újabb ilyen modern tudomány jött létre, ezek között szerepelnek pl. a biomatematika és a bioinformatika is. (A fizikán belül megjelentek pl. a földtudományok.) Ezen tudományágak fontossága magától értetődő, a mélységük azonban nagyon eltérő. Tapasztalatom szerint, amikor Lovász hidat épít, akkor ott mindig mély matematika jön létre. Emellett ezek más jellegűek: vagy a matematika két részét kötik össze, vagy néha az elméletet a gyakorlattal.

 – –

Nagyon szeretem a magyar matematikai közéletben, hogy megbecsüli azokat, akik nagy mértékben járultak hozzá a magyar matematikai élethez. A megbecsülés egyik formája, hogy születésnapjaikon egy előadássorozatot szervezünk, néha egy minikonferenciát, megint máskor egy nagyobb szabású matematikai összejövetelt.

Néha kicsit igazságtalanul több olyan embernek, barátnak, kiemelkedő magyar matematikusnak szervezünk közös születésnapi konferenciát, akik külön-külön is nagyon megérdemlik a konferenciát, de nem tehetünk semmit, mert egy évben egy területen gyakorlatilag csak egy ilyen konferenciát lehet jól megszervezni.

Az első ilyen születésnapi konferencia, amelyiken részt vettem, Erdős Pál 60. éves születésnapi konferenciája volt. Akkor ezt nem vettem komolyan, azt gondoltam, akartunk egy jó konferenciát szervezni, és milyen jó, hogy erre azt mondhattuk, hogy ez egy Erdős születésnapi konferencia volt. És, ha jól emlékszem, abból a szempontból igazam is volt, hogy a konferencia nem Erdős matematikájára koncentrált, emellett azonban egy kitűnő konferencia volt.

Lovász Laci születésnapi konferenciája két szempontból is kiemelkedő volt. Míg egy szokásos kombinatorika konferencia mérete 60 és 250 között szokott lenni, az óriás konferenciák létszáma elérheti a 300–500 résztvevőt is. Ilyen szempontból Laci konferenciája a legnagyobbak közé tartozott, persze mérete eltörpült egy orvos-konferenciához képest.

Egyedibb volt ehhez képest, hogy „gyakorlatilag” csak meghívott előadók voltak. (Technikai okokból voltak poszterek is, amelyeket a környezetemben nem nagyon szeretünk, de ugyanekkor formai szükség van rájuk: sokan csak akkor tudnak ideutazni, ha legalább egy poszter formájában aktív résztvevők. A költségeiket csak ekkor fedezhetik az elérhető forrásokból.) Akiket meghívtunk, azok mind kapcsolódtak valamilyen módon Laci matematikájához.

2. A Lovász-konferenciáról

A Building Bridges I–II konferenciákon, vagy az ezekhez némileg hasonló konferenciákon, pl. Szemerédi Endre születésnapi, vagy Erdős Pál, ill. Turán Pál emlékkonferenciáin nemzetközileg nagyon kiemelkedő matematikusok voltak az előadók, olyanok, akiket nagyon gyakran hívnak meg a legfontosabb konferenciákra, plenáris előadások tartására. Mindegyik meghívott nagy örömmel fogadta el a meghívásunkat.

A meghívottak listája: Noga Alon, Babai László, Anders Björner, Bollobás Béla, Christian Borgs, Sourav Chatterjee, Jennifer Chayes, Persi Diaconis, Uriel Feige, Jacob Fox, Jordán Tibor, Gil Kalai, Ravi Kannan, Peter Keevash, Nathan Linial, Jaroslav Nešetřil, Alexander Razborov, Lex Schrijver, Joel Spencer, Terry Tao, Tardos Éva, Tardos Gábor, Szőnyi Tamás, Szegedy Balázs, Szemerédi Endre, Santosh Vempala, Van Vu, Avi Wigderson, pontosabban, ők voltak, akik hosszú előadásokat tartottak, és a kiemelkedő fiatalok bemutatására volt még öt fele-hosszú előadás is. Csupa nemzetközileg nagyon elismert matematikus, Lovász munkásságához kapcsolódó területről. Persze, ha a konferencia nem lett volna behatárolva 5 napra, akkor még sok kitűnő matematikust hívtunk volna meg főelőadásra.

Az előadások és az előadók három csoportba oszthatók. A centrumot a kombinatorika-gráfelmélet (diszkrét matematika) jelentette. Ez a terület nagyon szoros kapcsolatban van, nagyon gyümölcsöző egymásrahatásban az elméleti számítógéptudománnyal. Számtalan olyan probléma jelent meg a modern matematikában, amely valahogyan egy gyakorlati problémában, vagy egy alkalmazásban bukkant fel, és érdekes matematikai problémákhoz vezetett. Az újdonság ezen a területen az, hogy míg régebben az alkalmazások egy jelentős részéről látszott, hogy fontosak, de nem voltak nagyon vonzóak, a kombinatorika és az elméleti számítógéptudomány kapcsolatában nagyon sok gyönyörű és matematikailag igen mély probléma jelent meg.

A fenti lista mindegyik szereplőjéről elmondhatjuk, hogy nemzetközileg nagyon elismert és nagyon szoros kapcsolatban van Lovász Lacival. Csak néhányat emelek ki. A mi szakterületünkön Noga Alon az egyik legelismertebb szaktekintély, a Tel Avivi Egyetemről, az ottani kombinatorika iskola felépítője. Ugyanez mondhatő el Bollobás Béláról is, csak ő Cambridge-ben hozott létre egy, az angol kombinatorikát nagyon meghatározó iskolát, majd ezt a munkát folytatta az USA-beli Memphisben.

Babai László, aki most a Chicagoi Egyetem professzora, de sok évig volt az egyik meghatározó személyiség az ELTE matematika oktatásában, aki egyébként Lovásszal, Sós Verával,... közösen hozta létre a világ egyik legelismertebb kombinatorika folyóiratát, a Combinatorica-t, Lovásszal közösen nagyon nagy hatással volt a Műegyetem matematikai és informatikai képzésének kialakításában, biztosítva annak a modernségét is. Babai egyébként nemrég bizonyított be egy nagyon fontos tételt, az alábbiakban kicsit el is magyaráznám.

Ha adott egy tulajdonság, és szeretnénk egy ilyen tulajdonságú gráfot találni, az elvben egyszerű lenne: felsorolnánk az pontú gráfokat, majd megnéznénk, hogy van-e közöttük tulajdonságú. Ez a valóságban azért nem működik, mert az pontú gráfok száma nagyon gyorsan nő: aránylag kis -re már évekig, vagy tízezer évig is várnunk kellene az eredményre. Ezzel tehát nem sokra jutnánk. Ezt nevezik kombinatorikus robbanásnak. Az egyik probléma a felsorolásban az, hogy ugyanazt a gráfot sokféle módon is előállíthatjuk. Ezért ezen a területen centrális fontosságú az izomorfia probléma: felismerni két gráfról, hogy azonosak, csak másként vannak elnevezve a csúcsaik. A legegyszerűbb esetben ez a következőt jelenti:

Adott két gráf, és , van-e olyan gráf-izomorfia, amelyik az egyiket átviszi a másikba.

De persze maga az izomorfia-probléma nem csak a gráfok generálásakor fontos. Azt sejtik, hogy nem tartozik sem a polinomiálisan megoldható, sem a legnehezebb polinomiálisan ellenőrizhető problémák közé, amelyeket NP-teljeseknek neveznek: ez a probléma valahol középen van.

Babai sok éven keresztül dolgozott ezen a problémán, és az utóbbi években egy döntő áttörést ért el: egy, a korábbiaknál sokkal-sokkal gyorsabb algoritmust talált a fenti kérdés eldöntésére. (Vigyázat, ez most nem egy, a gyakorlati alkalmazásokra kihegyezett eredmény. A fő kérdés az, hogy a fenti kérdés megoldható-e polinomiális sok lépéssel. Babai egy majdnem-polinomiális algoritmust talált.) Meglepő módon Babai a konferencián nem erről beszélt, hanem Lovász fiatalkori matematikájáról, ahogyan Lovász Laci elindult matematikai pályáján, és ahogyan híres lett.

Gil Kalai előadása a kvantumszámítógéppel kapcsolatos volt. Azt már tudjuk, hogy a mai típusú számítógépek nagyon sok dolgot soha nem lesznek képesek kiszámolni, az ún. kombinatorikus robbanás miatt. Például a titkosírásoknál nagyon fontos, hogy ha én két prímszámot, -t és -t összeszorzok, az eredményt, -t odaadom egy kitűnő szakembernek, ő vissza tudja-e keresni -t és -t? Ha pl. , akkor mindenki tudja, hogy , vagy . De mi van, ha 200 számjegyű prímekkel van dolgunk? Azt gondoljuk, jegyű prímek keresése sokkal könnyebb, mint két jegyű prím, szorzatából, -ból a két prím visszakeresése, azaz, változhat, hogy mekkora prímeket tudunk előállítani, de mindig sokkal nagyobb prímeket tudunk találni, mint amilyenek esetében -t fel tudjuk bontani. Ez a kérdés az egyik legmodernebb titkosítással közvetlen kapcsolatban áll, így a mi mindennapi életünkre is kihat, a jelszavaink, a bankkártyáink biztonságosságán keresztül.

Mármost, az utóbbi időkben elméleti szinten megalkották a kvantumszámítógépet, amelyik sokkal hatékonyabb az felbontásában. Ha meg tudnánk építeni egy ilyen gépet, az esetleg könnyen feltörné a titkosírásainkat. A tudósok egy része hisz a kvantumszámítógépek megépíthetőségében, a másik része nem. Gil Kalai erről beszélt.

Hasonlóan kiemelném Lex Schrijver holland matematikust, aki az amszterdami matematikai élet kiemelkedő személyisége, kitűnő matematikus, és fiatal korában csak azért jött Szegedre, és töltött el ott hosszabb időt, hogy Lovásztól tanulhasson matematikát. Ő is olyasmiről beszélt, ami Lovász matematikájával közvetlen kapcsolatban van.

Itt most igazságtalan leszek, azzal, hogy abbahagyom a fenti kíválóságok ismertetését. Viszont teszek még egy megjegyzést, az előadások hallgatóságáról. Kitűnő matematikusokból állt a hallgatóság is, fiatalok és idősebbek egyaránt megjelentek. Nem adhattak elő, így az, hogy eljöttek, duplán kifejezte Lovász iránti szeretetüket, tiszteletüket, és sok társszerző esetén a hálájukat is. Emellett persze nagyon élveztük, hogy egymással beszélgethettünk, matematikáról és sokminden másról is.

Ha valakit érdekelnek az előadások, azok filmfelvételenek többségét megtalálhatja a konferencia honlapján, a programban: https://www.renyi.hu/conferences/ll70/program/

3. Lovász matematikája, matematikai hatása

Lovász matematikája nagyon szerteágazó. Nem lehet néhány szóban leírni. Hallottam egy mondást, miszerint a matematikában David Hilbert és Henri Poincaré voltak az utolsó polihisztorok, azaz, akik koruk egész matematikáját értették, és átlátták. Nem tudom, hogy ez így van-e.

Ha visszamegyünk a 20. század elejére, akkor még léteztek olyan matematikusok, akik az egész matematika egy igen jelentős részéhez értettek, polihisztorok voltak. A matematika 20. századbeli fejlődésének egyik szükségszerű, kicsit elszomorító (?) következménye volt, hogy a polihisztorok eltűntek, a matematikusok egyre nagyobb része lett kíváló szakértője a matematika egy egyre kisebb részének.

Az én környezetemben, a professzoraim között talán még volt néhány polihisztor. Itt elsősorban Erdős Pálra, Turán Pálra, Rényi Alfrédra gondolok. De polihisztorok voltak pl. a szovjet iskolából a világhírű Kolmogorov, illetve Gelfand is...

A mostani magyar matematikusok között sokkal kevesebb a polihisztor, Lovász Laci mindenesetre egyike azoknak, akik nagyon sokoldalúak, és ez a matematikájában is meglátszik.

Szerintem egy matematikus megítélésében lényegtelen, hogy csodagyerek volt-e, vagy sem. A lényeget inkább abban keresném, hány olyan cikket írt, és hány olyan tételt bizonyított, amelynek elolvasása után érzem a cikk mélységét, a benne levő gondolatok és eredmények mélységét, és gyakran azok szépségét is. (A félreértések elkerülésére, itt megjegyzem, hogy szerintem a tudományos teljesítményt soha nem cikkszámmal, vagy impakt faktorokkal kell mérni. Cikkszámban Bernhard Rieman pl. nagyon lemaradna a mai matematikusok között. De magyar páldaképeink között is emíthető Gallai Tibor, aki nemzetközileg igen elismert, nagyhatású, és mai mércével nagyon kevés cikke volt.)

– –

Az én generációm igazán szerencsésnek érezheti magát, kitűnő tanáraink voltak, és kiemelkedően jó matematikusokkal voltunk körbevéve. Tanáraim közül, abban a sorrendben, ahogyan megismerkedtem velük, Sós Verát, Erdős Pált, és Turán Pált emelném ki, de Hajnal Andrástól és Fried Ervintől is nagyon sokat tanultam, matematikát és matematikai szemléletet. Ez a cikk azonban most nem róluk szól.

A sok kitűnő matematikus barátom, kollégám között talán ketten emelkedtek ki nagyon, Lovász és Szemerédi. Sorra bizonyítottak olyan tételeket, amelyektől a világnak „tátva maradt a szája a csodálkozástól”.

Lovász Lacival akkor ismerkedtem meg, amikor elsőéves egyetemista voltam, és egy szakköri előadást tartottam a Fazekas Gimnáziumban, az akkori elsős matematika tagozatos diákoknak. Máig is emlékszem, hogy a szakkör után Rábai Imre (a matematikatanáruk) kiemelte, hogy Lovász, Pelikán, Laczkovich, Berkes is nagyon jó matematikusok lesznek: addig még csak Pósa Lajos nevét ismertem.

Később, amikor Laci egyetemista lett, sokat beszélgettem vele matematikáról, nagyon sokat tanultam tőle, de erről azért nem írok, mert Laciról van most szó, nem rólam. Azt azonban kiemelném, hogy Laci nagyon odafigyel a környezetére, nagyon támogatja őket matematikai fejlődésükben, nagyon odafigyel a fiatalokra is, így magától érthetődően nemcsak nagyon nagy szakmai tiszteletnek örvend, hanem általános, hogy azok, akik ismerik, nagyon szeretik is.

– –

Egyszerűsítés struktúrák szorzatában. Lovász első meglepő és mély tétele a strukturák szorzatában való egyszerűsítésekről szólt. A legegyszerűbb esetekben ez azt jelenti, hogy struktúráknál ugyanúgy egyszerűsíthetünk, mint az egész számok körében. Mit is jelent ez?

A pozitiv egész számok körében, ha , akkor . Mátrixokra ez már nem igaz, kivéve ha extra feltételeket teszünk, pl. csak olyan négyzetes mátrixokra szorítkozunk, amelyek invertálhatók. De mi van, ha struktúrák szorzatánál szeretnénk egyszerűsíteni? Létezik az algebrának egy ága, az univerzális algebrák elmélete. Ez az absztrakt algebrai struktúrákkal és azokon végzett műveletekkel foglalkozik. Lovász első kiemelkedő eredménye éppen azt bizonyította, hogy ha veszünk három ilyen absztrakt struktúrát, -t, -t, és -t, akkor -ből következik , azaz, egyszerűsíthetünk. Ahhoz persze, hogy az előző mondat értelmes és igaz legyen, szükségünk lenne a tekintett struktúrák definiálására, a szorzat definiálására, és arra, hogy a fenti egyszerűsítési szabály igaz voltához még mit kell feltenni a Lovász-tételekben.

Ugyanezen 1967-es cikkében szerepel az a természetes kérdés is, hogy lehet-e struktúráknál négyzetgyököt vonni: -ből következik-e ? De Lovász nem áll meg itt, hanem tetszőleges polinomra megvizsgálja, hogy -ből következik-e .

Később, egy 1971-es cikkében Lovász visszatér ezekhez a kérdésekhez. A bizonyításai bizonyos homomorfizmusok (művelettartó leképezések) leszámlálásán alapulnak, és egy osztrák vezető gráfelmélész akkoriban éppen ezt emelte ki: azt magyarázta, hogy nem is az eredmények, hanem ezen homomorfizmus-sorozatok felhasználása volt, ami lenyűgözte őt ezekben a cikkekben. De ami igazán érdekes, hogy sokkal-sokkal később, amikor Lovász és társszerzői létrehozzák a gráflimeszek elméletét, akkor ugyanezen homomorfizmus-számolásokhoz térnek vissza, egy egészen más területen.

Lovász valószínűségi lemmája. Kombinatorikában és gráfelméletben Erdős Pál alakította ki azt a módszert, ahol valamilyen tulajdonságú objektum létezését úgy bizonyította, hogy véletlen objektumokat (mondjuk, gráfokat) generált, és bebizonyította, hogy pozitív valószínűséggel, a generált objektum rendelkezik a tulajdonsággal. Márpedig ez csak úgy lehet, ha van legalább egy ilyen objektum.

Az ilyen bizonyításoknál gyakran előfordul, hogy amennyiben az események valószínűségszámítási értelemben függetlenek lennének, akkor a közös bekövetkezésük valószínűsége a valószínűségük szorzata lenne, és ettől pozitív lenne. Sajnos azonban ezek az események igen gyakran nem függetlenek. Erre vezette be Lovász (egy Erdőssel közös cikkben) azt, amit ma Lovász Local Lemmának hívunk, és aminek az a tartalma, hogy ha az események valamilyen matematikailag jól definiált értelemben csak gyengén függnek egymástól, akkor majdnem ugyanúgy kezelhetjük őket, mintha függetlenek lennének, és ezért közös bekövetkezésük pozitív valószínűségű. Az alábbiakban megfogalmazom a lemmát, majd egy rövid kiegészítő magyarázatot is adok, de ha valaki idegenkedik az egyébként gyönyörű valószínűségszámítástól, az nyugodtan ugorja át.

Lovász Local Lemma. Egy valószínűségi térben legyen adott „rossz” esemény, . Tegyük fel, hogy van olyan gráf a csúcsokon, amelyik az események függetlenségét tükrözi: mindegyik független azon -k együttesétől, amelyekre nincs összekötve -vel. Tegyük fel továbbá, hogy a gráf ritka: ha mindegyik valószínűsége legfeljebb , akkor a gráf maximális foka legfeljebb . Ilyenkor pozitív annak a valószínűsége, hogy egyik sem következik be.

A lemma egyszerűnek tűnik, majdnem triviálisnak, a bizonyítása is csak egy oldal, a mélyebb megértése talán kicsit nehezebb. Megpróbálom elmagyarázni. Adott egy pontú véletlen gráf, és ezen nagyon sok, esemény, . Ezek a „rossz” események, és mi egy olyan létezését szeretnénk bebizonyítani, ahol egyik „rossz” esemény sem következik be. Ha az események függetlenek volnának, és mindegyikük valószínősége 0.01 alatt maradna, akkor a lemma feltétele az lenne, hogy legyen egy olyan „függetlenségi gráf”, amelynek maximális foka legfeljebb . Ez egy kicsit több annál, hogy mindegyik esemény csak legfeljebb 25 másikkal függ össze. A finom különbség abban rejlik, hogy elképzelhető az, hogy egy esemény 25 másik eseménytől egyesével független, de az együttesüktől nem, sőt, az együttesükből ki is számolható. Ha pl. három dobókockával dobálunk, de csak azokat a dobásokat tartjuk meg, ahol az összeg páros, akkor bármely két dobás független, de a három dobás már nem független.

Tipikus eset a fentiekre, hogy ha mondjuk van egy szögpontú gráfunk, és azt szeretnénk kiszámolni, hogy mi a valószínűsége annak, hogy a gráfban legyen egy pontú kör, akkor a potenciális körök száma.

A lemma megszületése óta nagyon elterjedt a használata, és algoritmikus változatának kidolgozása (Marcus–Tardos) is igen fontos volt.

Gráf-limesz. Ahogyan a racionális számokból létrejönnek a valós számok, ahhoz hasonló, ahogyan a gráfsorozatoknál is bevezethető egy konvergencia, a gráfsorozatok limesze. Ezzel létrejött az utóbbi, mondjuk, 15 évben egy egészen új elmélet. Ahogyan a valós számoknál fontos a Cauchy-konvergenciakritérium, a gráfsorozatoknál is valami ehhez hasonlóra van szükségünk. Nem mennék bele a részletekbe, csak annyit mondanék, hogy ezen a területen a kutatás akkor indult el, amikor Lovász a Microsoft Research-nél dolgozott, Redmondban, Washington államban, és a téma első fontos cikkeit itt írták meg, Lovász, Szegedy Balázs, Sós Vera, Vesztegombi Kati, Borgs és Chayes. Ma már ez egy nagyon kiterjedt kutatási terület, célzott konferenciákkal, és Lovász ebből a témából (is) írt egy óriás-monográfiát.

– –

Lovász matematikájáról, összefoglalóan. A fentiekben felvillantottam Lovász matematikájából három részletet, de nem beszéltem a perfekt gráfokról, a Shannon-kapacitásról, a Kneser-gráf kromatikus számáról, az algoritmikus eredményeiról, és még sok más sikeréről. Laci matematikája nagyon sokoldalú. Sokoldalú témaválasztásban, és sokoldalú a módszereiben is. A számtalan meglepő és sikerre vivő ötlete mellett nagyon fontos az a tisztánlátás és mélyenlátás, amely Lovász Laci egész munkásságát jellemzi. Ez jellemzi a bizonyításait, a cikkeit, a könyveit és a beszélgetéseit a környezetével.

Lovász Magyarországon és nemzetközileg is igen elismert, ezt jelzi a számos díja, kitüntetése, az, hogy az International Mathematical Union elnökévé választották. Mindezekről azért nem írok, mert a magyar Wikipédia oldalon is kitűnően fel vannak sorolva.

– –

Lovász László nem-matematikai érdeklődése is igen széles. Szereti a fizikát, és általában minden tudományos elmélet érdekli. Szeret kirándulni, szeret olvasni, szereti a zenét, szeret szerelni, szóval, semmiképpen sem egy beszűkült matematikus, aki csak a képleteivel bajlódik.

– –

Miközben ezeket a sorokat írom, tudom, hogy Lovász Lacinak most éppen nem könnyű az élete, mert a Magyar Tudományos Akadémia elnökeként nagyon nagy a felelőssége, és nagyon nehéz kérdésekben kell döntenie.

Mindenképpen jó egészséget és sok boldog születésnapot kívánok Lovász Lacinak.