VIII. szemeszter, 2006. május 15. – 11. előadás

KATONA GYULA

HOGYAN LETT "MAGYAR MATEMATIKA" A KOMBINATORIKA?

A matematikának vannak olyan területei, ahol a magyar kutatások a világ élvonalába tartoznak. Erdős Pál elődei és utódai például jóformán "magyar tudománnyá" tették a kombinatorikát. Ez a tudományág eredetileg játékos, rejtvényszerű problémákon alapult, a számítógép megjelenésekor azonban kiderült, hogy a kombinatorika a számítástudomány egyik alapja. Ennek köszönhető, hogy az utóbbi időben robbanásszerű fejlődésnek indult. A kombinatorikának ráadásul megvan az az előnye, hogy viszonylag könnyen bemutatható laikusoknak is. Az előadás az elmúlt 40 év fontos hazai eredményei közül ismerteti azokat, melyek bonyolult képletek nélkül is jól szemléltethetők.

I. A KOMBINATORIKA MÚLTJA ÉS JELENE

Hallunk néha olyan állításokat, hogy a magyar matematika világhíres. Igaz ez? Ki merem jelenteni, hogy igen. Persze egy tízmilliós nemzet nem vetekedhet az amerikaiakkal, oroszokkal, sőt az angolokkal, németekkel, franciákkal sem. A hasonló méretű népek közül talán csak a lengyelek versenytársaink. Kicsinységünk miatt csak a matematika néhány területén tudunk kiemelkedőt alkotni. De ott igen! Ezek a kiemelkedő területek korszakról korszakra változnak. Az utóbbi fél évszázadban a kombinatorika ilyen terület volt. Erre az állításra fogok most néhány "bizonyítékot" szolgáltatni. A magyar matematikának más területeken is vannak, voltak kiemelkedő eredményei, egyéniségei, de én most csak a kombinatorikáról fogok beszélni, mert egyrészt azt nagyjából el lehet mondani nem matematikusoknak is, másrészt ahhoz értek.

A kombinatorika már a 16. században megjelent, de igazi fejlődésnek csak a 20. században indult - jelentős részben magyar matematikusoknak köszönhetően. A második világháború előtt és után sok szép eredmény született. Ezeket azonban nem az alkalmazások kényszerítették ki. A megoldott problémák többnyire játékosak, fejtörő jellegűek voltak: érdekesek és nehezek, vagyis nagy kihívást jelentettek. Erdős Pál az egyik fontos eredményét 1938-ban találta ki, de csak 1961-ben jelentette meg, mert úgy gondolta, hogy azt mások nem tekintik matematikának. Amikor a számítógépek megjelentek, néhány év után kiderült, hogy a kombinatorikát, más néven a véges matematikát igénylik. Akkor indult be az igazán rohamos fejlődés. És a magyar matematika azóta is tartja helyét e területen. Itt dolgozik, illetve dolgozott két olyan világhíresség, mint a Mindentudás Egyetemének egy korábbi előadója, Lovász László és Erdős Pál. A kombinatorikát sokan máig "magyar tudománynak" tartják a világban. Az 1970-es, 1980-as években volt egy amerikai mondás - recept arra, hogy hogyan csináljunk számítástudományi tanszéket: "1. Végy egy magyart!"

Előadásomban az utóbbi 50 év fontos magyar kombinatorikai eredményeiből válogattam saját ízlésem szerint, és aszerint, hogy mit lehet itt rövid idő alatt elmondani. Mindegyik legalább 30 éves. Ennyi idő kell, hogy egyértelműen kiderüljön egy matematikai eredmény fontossága.

II. MENNYI MADONNA LATABÁR-SZÁMA?

Kezdjük gráfelmélettel, amiről valószínűleg sokan hallottak már, de jobb lesz néhány példával kezdeni. A gráf valamilyen elemek, tárgyak, személyek közötti kapcsolatokat ír le. Például egy társasági összejövetel résztvevői között vannak olyan párok, akik ismerik egymást, más párok nem. Ezt le is tudjuk rajzolni, ha az egyes embereket pontokkal, az "ismeretséget" egy összekötő vonallal jelképezzük.

Egy jól ismert gráf-fajta a kémiai kötéseké. Az atomokat betűkkel jelöljük, az összekötő vonalak a kémiai kötéseket mutatják.

De lehet a világ összes emberét egy-egy ponttal ábrázolni, s kettőt összekötni, ha legalább egyikük arcról ismeri a másikat.

Két ember távolságának azt nevezzük, hogy hány lépésben lehet a gráfban az egyiktől a másikig eljutni. Azaz akik össze vannak kötve, azok távolsága egy. Ha kettő nincs összekötve, de van közös ismerősük, akkor távolságuk kettő s így tovább. Itt már bátran feltehetünk egy kérdést is: mi a legnagyobb távolság az emberek között? A mai világban valószínűleg 2! Ugyanis bizonyára mindenki ismeri Bill Clintont. Na jó, ha nem szokott tévét nézni, akkor ismer valakit, aki szokott. Akkor is legfeljebb 4 lépésben el lehet jutni egyik embertől a másikig.

Egy tréfás változat, amit matematikusok találtak ki maguknak, a következő. A pontok matematikusokat jelentenek, két ilyen pont össze van kötve, ha az illető matematikusoknak van közös tudományos publikációjuk (cikkük). Ezt arra találták ki, hogy megállapítsák az ún. Erdős-számot, ami azt jelenti, hogy ebben a gráfban hány lépés van Erdős Páltól az illetőig.

A következő animáción ennek a gráfnak egy részletét láthatjuk. A legbüszkébbek azok, akiknek az Erdős-számuk 1, azaz van közös cikkük Erdőssel. Íme néhány nevezetes Erdős-út (a zárójelben az Erdős-számok szerepelnek):

Erdős Pál (0) - P. Hell (1) - Xiao Tie Deng (2) - C. H. Papadimitriou (3) - Bill Gates (4)
Erdős Pál (0) - E. Straus (1) - Albert Einstein (2)
Erdős Pál (0) - Csiszár Imre (1) - Katona Gyula (2)

De a művészek sem maradnak már le. Az amerikai fiatalok körében népszerű Kevin Bacon-játékban a pontok színészek, kettő össze van kötve, ha játszottak egy közös filmben. Itt is meg lehet kérdezni, hogy mennyi két színész távolsága. Ha például azt kérdezzük, hogy milyen messze van egymástól Latabár Kálmán és Madonna, arra az eredményre jutunk, hogy Madonna Latabár-száma 3. Erről mindenki maga is meggyőződhet az alábbi link segítségével: http://oracleofbacon.org/star_links.html (Megjegyzés: a keresésnél ne használjunk ékezetet: "Kalman Latabar", Madonna nevét pedig így használjuk: "Madonna (I)".)

III. VÉLETLEN GRÁFOK

A matematikán belül a gráfelmélet egy hatalmas és szerteágazó terület, melyből ez alkalommal csak a véletlen gráfokról fogok szólni. Sok esetben az összekötések véletlenül jönnek létre. Például amikor egy folyékony anyag megfagy, akkor a molekulák között véletlen kapcsolatok jönnek létre. De még jobb példa az internet. Hogy két internetező pont között létrejött-e kapcsolat, az eléggé véletlen. Erdős Pál és Rényi Alfréd az 1960-as években, amikor még számítógép is alig volt, nemhogy internet, kidolgozták a véletlen gráfok elméletét.

Csináljunk most egy ilyen véletlen gráfot a számítógéppel. Legyen n=32 pontunk, és kezdetben ne legyen egyetlen él se közöttük. Azért választottuk a 32-t, mert az a 2 ötödik hatványa, azaz a 32 kettes alapú logaritmusa 5, s ennek szerepe lesz a továbbiakban. Az elmélet kritikus értéke lesz, ami itt:

.

Most vegyünk két pont között egy élet véletlenül, az összes lehetséges élből egyforma valószínűséggel. Most vegyünk még egyet a maradék, még ki nem választott élek közül, ismét egyforma valószínűséggel és így tovább. Mindig egyforma valószínűséggel vegyünk egyet a még nem választott élek közül. Így persze minden egyes gráfhoz eljuthatunk, és ugyanazzal a valószínűséggel, de ha a gráf bizonyos tulajdonságát, formáját nézzük, akkor már észre fogjuk venni, hogy bizonyos formák gyakoribbak, mint más formák.

Ismernünk kell két fogalmat: egy gráf összefüggő, ha bárhonnan bárhova el lehet benne menni az éleken. A 8. ábrán példaként egy összefüggő és egy nem összefüggő gráfot mutatunk be. A nem összefüggő gráfban egy összefüggő részt komponensnek hívunk. A bemutatott példában a komponensek száma 3.

Folytassuk a véletlen élek hozzáadását! Körülbelül 32/2=16 lépés után jelenik meg az első kör a gráfban. A következő példa egy 32 pontú gráf 31 éllel, amiben nincs kör. De véletlen gráfban nagy valószínűséggel már 16 után lesz kör. Azután a kritikus szám, 80 körül válik a gráf összefüggővé. Előbb azonban olyan lesz, hogy lesz egy nagy komponense, amiben majdnem minden pont benne van, e mellett egy néhány magányos pont áll. Itt az a fontos, hogy meg tudjuk mondani, hogy körülbelül hány élnél lesz a gráf összefüggő, ha az éleket véletlenül választottuk. A fenti fogalmazásban többször mondtam olyanokat, hogy "körülbelül" meg "nagy valószínűséggel". Ezek pontos értelmét már csak bonyolult képletekkel lehet megadni.

Ma már az elmélet meg tudja adni a véletlen gráfok sok más tulajdonságát is. Az alkalmazásoknál viszont fel tudjuk tenni, hogy csak bizonyos éleket választhatunk ki véletlenül, a többi nem szerepelhet egyáltalán. Itt utalok Csermely Péternek Hálózatok sejtjeinkben és körülöttünk címmel a Mindentudás Egyetemén korábban elhangzott előadására.

Az eddigiekben azt láttuk, hogy a véletlen gráfok tulajdonságai is leírhatók, de mások, mint a szándékosan készített, nem véletlen gráfoké. Ezek után meglepő lehet az az állítás, hogy minden gráf bizonyos értelemben véletlen. Márpedig Szemerédi Endre akadémikus 1970-es évekből származó híres tétele így is fogalmazható. Egy gráfról azt mondjuk, hogy kupacosan véletlen, ha a pontjai egyforma kupacokba oszthatók úgy, hogy bármely két kupac közötti élek úgy helyezkednek el, mintha véletlenül választottuk volna őket.

Szemerédi tétele - igen pontatlanul fogalmazva - azt mondja ki, hogy ha egy gráfnak legalább egymilliárd pontja van, akkor az felbontható ezer és ötezer közötti számú kupacra úgy, hogy a kupacok közötti élek úgy viselkednek, mintha véletlenek lennének. Persze a tétel pontos kimondásához meg kellene mondani pontosan, mikor mondjuk azt, hogy két kupac között az élek véletlennek néznek ki, és meg kellene mondani, hogy kaptuk az ezer, ötezer és milliárd számokat. De a lényeg az, hogy egy tetszőleges gráfban is található valamilyen jól használható rendszer, ha a pontok száma nagyon nagy. Ennek a tételnek még nincsenek gyakorlati alkalmazásai, de igen fontos az elmélet számára. Manapság is nagyon sok, nehéz, sokáig megoldatlan problémát oldanak meg a segítségével.

IV. SAKKJÁTSZMÁK PÁROSÍTÁSA - AVAGY MIÉRT KELLETT ELHALASZTANI AZ 1883-AS NÜRNBERGI TORNÁT?

A sakkversenyek rendezéséhez is kell gráfelmélet. A játékosok a pontok, az összekötések

a játszmák. Tegyük fel, hogy páros sok versenyzővel akarunk körmérkőzést lebonyolítani. Azt szeretnénk, hogy minden nap mindenki játsszék valakivel, és néhány nap után előálljon az a helyzet, hogy mindenki mindenkivel pont egyszer játszott. Most azzal nem törődünk, hogy hányszor játszottak világossal. n=6 esetén ezt a következő animáción bemutatott módon lehet megoldani.

De nem olyan nyilvánvaló, hogy ezt meg lehet csinálni! Például a rossz versenyrendező az első három fordulóban így játszatta a játékosokat:

Ekkor a negyedik forduló nem tehető teljessé. Ugyanis minden olyan mérkőzést lejátszottak már, ahol a fenti sorrendben szomszédos vagy szemközti játékosok sakkoznak. Tehát a negyedik forduló párosításában egymástól csak második helyen levők játszhatnak. Ilyenekből azonban nem hozható ki egy teljes forduló, azaz 3 olyan párosítás, amiben 6 különböző játékos van. Ezért már régen táblázatok alapján rendezik a versenyeket. Nagy feltűnést keltett, amikor 1883-ban a Nürnbergi Torna kezdését el kellett halasztani, mert Schallopp nagymester, a táblázat készítője otthon felejtette a táblázatot. Persze a matematikában már akkor ismert volt, hogyan kell ezt megcsinálni.

Most képzeljük el, hogy 6 ember - jelöljük őket A, B, C, D, E, és F betűkkel - el akarja dönteni, hogy melyikük a legjobb ultijátékos, úgy, hogy mindig hárman ülnek le játszani. Hogyan lesz ez igazságos? Úgy, ha minden egyes játékos kipróbálhatja erejét bármely másik kettő ellen. Azaz bármelyik hármas részt vesz pontosan egy meccsen. Ha egy fordulóban valamelyik 3 mérkőzik, velük egyidejűleg a másik három is mérkőzhet egymással. Mivel a hármasok száma pontosan 20, egy fordulóban két hármas játszik, a fordulók száma legalább 10. A következő animáció segítségével könnyen belátható, hogy 10 fordulóban ezt meg is lehet csinálni.

Na és ha 30-an vannak? Vagy valamilyen más számnyian, ami 3-mal osztható? Ugyanis ez a feltétel kell, csak ekkor tudunk egy igazi teljes fordulót kialakítani.

Menjünk tovább az igazi magyar játéktól egy volt magyar játékra, a futballra! Mi van, ha 60 fiatal hasonlóan akarja eldönteni, hogy ki a legjobb futballista? 6-os csoportokban küzdenek, kapus nélkül kispályán, a legtöbb gólt rúgó nyer egy ilyen mérkőzésen. Meg lehet-e ezt szervezni a lehető legkevesebb teljes fordulóban úgy, hogy minden 6-os csoport pontosan egyszer játsszék? Sylvester angol matematikus az 1850-es években azt sejtette, hogy igen. Ez mindig megtehető, ha az egy meccsen szereplő játékosok száma osztja az összes résztvevő számát. Ezt az akkor 120 éves problémát oldotta meg 1975-ben, 28 évesen Baranyai Zsolt.

Baranyai nem volt matematikai csodagyerek. A versenyeken sosem szerepelt jól. Csak egy rendkívül szimpatikus, világos fejű fiatal volt, az ország egyik legjobb furulyása. Az 1972-es "Ki mit tud?"-on a szóló zene kategóriában második lett, csak egy hegedűs tudta megelőzni, Pernye András nem győzte őt dicsérni.

Nálam írta szakdolgozatát matematikából. Mivel abban már volt egy kisebb jelentőségű új matematikai eredmény, utána adtam neki egy másik - azért már nehezebb - problémát, ami nem látszott sem túl fontosnak, sem túl nehéznek. Néhány hónap alatt megoldotta. Akkor derült ki, hogy a probléma lényegében Sylvester 120 éve megoldatlan sejtése volt, csak egy más formában. Ha tudtam volna, nem tanácsoltam volna neki, hogy azzal a reménytelen problémával vesztegesse az idejét. Sajnos 2 év múlva autóbalesetben meghalt.

Ez a probléma jó példa arra, mit neveztem játékosnak, rejtvényszerűnek. A bajnokságos mese csak illusztráció, hogy könnyebben megérthessük. Valójában erre nem is használjuk, csak egy könnyen megfogalmazható szép állítás. A kihívás az volt, hogy be kellett bizonyítani. Azóta persze tudjuk, hogy alapvető jelentősége van sok más matematikai tétel bizonyításában.

V. A HALMAZOK "ÁRNYÉKVILÁGA"

Végül szerénytelen leszek: Egy 1965-ben született eredményemet mutatom be. Most már nem fogok csapatokról és hasonlókról beszélni. A kedves olvasók már gyakorlottak lettek, azt hiszem, beszélhetek már egyszerűen halmazokról.

Egy háromelemű halmaz árnyékhalmazai azon kételemű halmazok, amelyek egy-egy elem elhagyásával keletkeznek.

Tehát a háromelemű halmaznak 3 árnyékhalmaza van. Ha két háromelemű halmazom van, akkor ezek árnyékhalmazai egybeeshetnek (feltéve, hogy a két háromelemű halmaznak van közös eleme). Nézzünk két esetet! Az összes árnyékhalmaz száma lehet 6 is és 5 is.

Látható, hogy kevesebb nem lehet. Válasszunk most 3 darab háromelemű halmazt! Mikor lesz az összes árnyékhalmaz száma a legkevesebb? Érezhető, hogy akkor, ha a halmazokat "közel" vesszük. Ez 7 árnyékhalmazt ad, ez pedig csak 6-ot.

De bárki el tudná helyezni a három halmazt úgy, hogy 9 árnyékhalmazt kapjunk (segítség: a halmazokat egymástól a "legtávolabb" kell felvenni).

Tegyük fel, hogy mondjuk ezer háromelemű halmazunk van. Az összes árnyékhalmazt együtt nevezzük árnyéknak. Hogyan kell elhelyezni az ezer háromelemű halmazt úgy, hogy az árnyék a legkisebb legyen? Az eddigi példák alapján érezhető, hogy minél "közelebb" kell őket venni. Rajzoljunk most másképpen. Számozzuk meg az elemeket, amikből a halmazokat csináljuk, az egyszerűség kedvéért vegyünk csak 5 elemet: 1, 2, 3, 4 és 5. Ekkor például a 2, 3 és 5 elemekből álló halmazt a 13. ábrán látható módon ábrázolhatjuk (piros színű pontok).

A többi halmazt úgy ábrázoljuk, hogy egymás alá rajzoljuk őket különböző sorokba. Sok halmazt úgy tudunk egymáshoz "közel" venni, ha őket minél előbbre vesszük ebben az ábrázolásban. Ezt az ábrázolási módot lexikografikusnak nevezzük.

Ekkor az árnyékhalmazok a következők lehetnek: 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5. Érezhető, hogy ez a legjobb elrendezés. És valóban ez a legjobb. Persze akármilyen fix méretű halmazokra három helyett, és akárhány ilyen halmazra. A tétel általános formában a 15. ábrán látható.

De egyáltalán nem könnyű bebizonyítani, hogy ez a legjobb! Az első bizonyítások 20-30 oldalból álltak, de ma - negyven év után - már van 3-4 oldalas is. Igen sok helyen alkalmazták, az algebrai geometria mély elméletétől az elektromos hálózatok megbízhatóságának tervezéséig.

Valószínűleg feltűnt a hallgatóságnak, hogy egy másik név is látható a tétel mellett, Kruskal amerikai matematikusé. Ő néhány évvel előbb vette észre, és bizonyította be a tételt, mint én. Mégis majdnem az történt vele, ami a szegény kelet-európaiakkal szokott történni. Sok olyan történetet ismerünk, amikor a magyar, orosz, román tudós előbb fedez fel valamit, a nyugati később, a keleti név elfelejtődik, mert a nyugati jobban benne van a nemzetközi körforgásban, s végül az eredmény a nyugati tudós nevéhez kapcsolódik. Itt ez majdnem fordítva történt. Kruskal rossz helyen közölte eredményét, konferenciákra nem járt, senki sem tudott róla. Engem mint a magyar kombinatorikai iskola tagját már a húszas éveimben sok helyre hívtak meg előadni, az eredményt én terjesztettem a világban. Kruskal cikkéről csak később szerzett tudomást a tudományos közvélemény.

Végül egy alkalmazásról szólnék. Haraszti Attilával, Marsovszky Lászlóval,
Csirmaz Lászlóval, Miklós Dezsővel és Nemetz Tiborral kidolgoztunk egy azonosító bélyeget, amely dokumentumok vagy például hitelkártyák azonosítására szolgál, és amely a digitális vízjel elnevezést kapta. A bélyegen kis gömbök vannak, azok alapján történik az azonosítás. Kiderült azonban, hogy a leolvasásánál egyes gömbök eltűnnek. Azaz a gömbök halmazának árnyékai alapján kell az azonosítást elvégezni. A digitális vízjelről szól a következő filmrészlet.

Ehelyütt sem az azonosítás technikáját, sem a matematikai hátteret nem áll módunkban részleteiben megismerni, csupán azt reméltem érzékeltetni, hogy hogyan kerül elő itt is a halmazok árnyéka.

Előadásomban a kombinatorika magyar vonatkozású eredményei közül válogattam, a teljesség igénye nélkül. Remélem, sikerült átadnom valamit ebből az érdekes és izgalmas kutatási területből, és hadd reméljem, hogy az előadás nézői, olvasói között vannak olyan leendő matematikusok, akiknek eredményeit 50 év múlva valami hasonló előadásban fogják ismertetni. Persze az előadás technikai módszere bizonyára egészen más lesz. Talán a hallgatók mindegyike saját maga futtat majd illusztrációs programokat...

Bibliográfia

Andrásfai B.: Ismerkedés a Gráfelmélettel, Budapest, Tankönyvkiadó, 1973.
Gráfelméleti alapfogalmak, speciális gráfok és azok tulajdonságai. Elsősorban azoknak, akik komolyabban érdeklődnek a téma iránt. (magyar)

Lovász L.: Kombinatorikai problémák és feladatok, Budapest, Typotex, 1999.
A könyv elméleti és gyakorlati problémák megoldásán keresztül nyújt betekintést a kombinatorikai világába. Matematikus olvasók előnyben! (magyar)

Strehó M.: "A lényeg, hogy érdekes matematikával tudjam tölteni az időmet": Beszélgetés Bollobás Béla matematikussal, az MTA külső tagjával, In: Magyar Tudomány, 2000. 4.
Interjú a Nagy-Britanniában és az Egyesült Államokban dolgozó világhírű matematikussal az 1999-es budapesti Erdős-emlékkonferencia alkalmával. (magyar)

Katona Gy., Recski A., Szabó Cs.: A számítástudomány alapjai, Budapest, Typotex, 2003.
Egyetemi előadásokat összefoglaló munka a véges matematika, a kombinatorika, a gráfelmélet, az absztrakt algebra tárgyköréből. (magyar)

Rényi A.: Ars Mathematica, Budapest, Typotex, 1998.
Rényi Alfrédnek, a magyar valószínűségszámítás atyjának összegyűjtött írásai a matematikáról élvezetes, népszerűsítő formában. (magyar)

Staar Gy.: A megélt matematika: Beszélgetések, Budapest, Gondolat, 1990.
Olvasmányos interjúkötet világhírű matematikusokkal. Hogy pontosan kikkel? Íme a teljes névsor: Erdős Pál, Szemerédi Endre, Lovász László, Weszely Tibor, Tóth Imre, Szénássy Barna, Fejes Tóth László, Szőkefalvi-Nagy Béla, Császár Ákos, Lennart Carleson, Roland Lvovics Dobrusin, Jakov Grigorjevics Szinaj, Benoit B. Mandelbrot, William R. Wade, Kárteszi Ferenc, Fried Ervin. (magyar)

Bell, E. T.: Men of Mathematics, New York, Simon and Schuster, 1937, 1986.
A több kiadást is megélt, ismert tudománytörténeti munka végigvezet a matematika történetén. A kötet felvonultatja a matematika nagyjait az ókortól napjainkig. Inspiráló olvasmány egy matematikus tollából. (angol)

Demetrovics J., Katona Gy.: Az algoritmusok bonyolultsága, In: Természet Világa, Vol. 131 (II. különszám), 2000: 9-13.
Ízelítő a cikkből: "Mi az, hogy algoritmus? Amikor Clinton elnök szaxofonozik, és Al Gore alelnök az ujjaival dobol hozzá az asztalon. (...) A Sátán megkísérti a számítástudóst: - Pénzt adok, gazdagságot, tied lesznek a legszebb nők, a legjobb kocsik, ha engem szolgálsz. A tudós elgondolkodik, nagyon szeretne gazdag lenni, nem is szólva a nőkről. De a becsület! Mégis, van valami, amiért érdemes eladni a lelkét. - Rendben, a te szolgád leszek, ha..."Akit érdekel a befejezés, olvassa el a cikket, de végig! Megéri az odafigyelést. (magyar)