Kupacos véletlen

Hallunk néha olyan állításokat, hogy a magyar matematika világhírű. Igaz ez? Kijelenthetjük, hogy igen. Persze egy tízmilliós nemzet nem vetekedhet az amerikaiakkal, az oroszokkal, sőt az angolokkal, németekkel, franciákkal sem. Kicsinységünk miatt csak a matematika néhány területén tudunk kiemelkedőt alkotni. E területek korszakról korszakra változnak. Az utóbbi fél évszázadban a kombinatorika ilyen terület volt. Ezekkel a gondolatokkal kezdte előadását Katona Gyula matematikus a Mindentudás Egyetemén ezen a héten.

A kombinatorika már a XVI. században megjelent, de csak a XX. században indult igazi fejlődésnek – jelentős részben magyar matematikusoknak köszönhetően. A második világháború előtt és után sok új eredmény született, ám ezeket nem az alkalmazhatóságuk kényszerítette ki. A megoldott problémák többnyire játékosak, fejtörő jellegűek voltak. Erdős Pál 1938-ban találta ki egyik fontos megoldását, 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. Ekkor indult be az igazán rohamos fejlődés, s a magyar matematika azóta is tartja helyét e területen. Kombinatorikai problémákkal foglalkozik például egy másik világhíresség, Lovász László, a Mindentudás Egyeteme korábbi előadója is. A kombinatorikát sokan máig „magyar tudománynak” tartják a világban. Az előadás válogat az utóbbi 50 év fontos magyar kombinatorikai eredményeiből. A példák mindegyike legalább 30 éves. Ennyi idő kell ugyanis, hogy egyértelműen kiderüljön egy matematikai eredmény fontossága.
Kezdjük a gráfelmélettel, amelyről valószínűleg sokan hallottak már. Néhány példával világítsuk meg a lényegét! A gráf 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, amelyek ismerik egymást, illetve olyanok is, amelyek nem. Ezt le is tudjuk rajzolni, ha az egyes embereket pontokkal, az „ismeretséget” egy összekötő vonallal jelképezzük. Jól ismert gráffajta a kémiai kötéseké. 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. Akik ismerik egymást, tehát össze vannak kötve, azok távolsága egy. Ha ők nem ismerik egymást, 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 kettő. Például bizonyára mindenki ismeri Bill Clintont. Na jó, ha nem szokott tévét nézni, akkor ismer valakit, aki szokott. Vagyis akkor is legfeljebb négy lépésben el lehet jutni egyik embertől a másikig.
Van egy tréfás változat, amelyet matematikusok találtak ki maguknak. Itt a pontok matematikusokat jelentenek. Ha két pontot összekötünk, akkor az illető matematikusoknak van közös tudományos publikációjuk. Így állapítható meg az úgynevezett Erdős-szám, amely azt jelenti, hogy a gráfban hány lépés van Erdős Páltól az illető tudósig. A legbüszkébbek azok, akiknek az Erdős-számuk egy, azaz valamikor közös cikket publikálhattak Erdőssel. Albert Einstein Erdős-száma például kettő volt, hiszen közös cikket írt Ernst Strausszal, aki viszont Erdős szerzőtársa volt. Hasonló módon akár Bill Gates, a Microsoft vezetője is összeköthető a magyar matematikussal, aki három másik szerzőn keresztül négyes Erdős-számmal rendelkezik.
De a művészek sem maradnak le. Az amerikai fiatalok körében népszerű Kevin Bacon-játékban a pontok színészek. Ha kettőt összekötünk, akkor játszottak közös filmben. Ha például azt kérdezzük, milyen messze van egymástól Latabár Kálmán és Madonna, arra a talán meglepő eredményre jutunk, hogy Madonna Latabár-száma három.
A matematikán belül a gráfelmélet hatalmas és szerteágazó terület, amelyből ezúttal csak a véletlen gráfokról fogok szólni. Ilyen gráfok akkor születnek, ha a pontok közötti összekötések véletlenül jönnek létre. Például amikor egy folyékony anyag megfagy, a molekulák között véletlen kapcsolatok jönnek létre. Még jobb példa az internet. Hogy két internetező pont között létrejön-e kapcsolat, az meglehetősen nagy mértékben múlik a véletlenen. 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, kidolgozta a véletlen gráfok elméletét.
Csináljunk most 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.
Most vegyünk két pont között egy élet véletlenszerűen, az összes lehetséges élből egyforma valószínűséggel. Majd 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. Ilyen módon persze eljuthatunk minden egyes gráfhoz, és ugyanazzal a valószínűséggel, de ha a gráf bizonyos tulajdonságait nézzük, észre fogjuk venni, hogy egyes formák gyakoribbak, mint mások. Véletlen gráfban nagy valószínűséggel már 16 után lesz egy kör. Azután a kritikus szám, 80 körül válik a gráf összefüggővé, tehát olyanná, hogy bárhonnan bárhova el lehet benne menni az éleken keresztül. Előbb azonban a nem összefüggő gráfban lesz egy összefüggő rész, egy úgynevezett komponens, amelyben majdnem minden pont benne van, mellette néhány magányos pont áll. Itt az a fontos, hogy meg tudjuk mondani, körülbelül hány élnél lesz a gráf összefüggő, ha az éleket véletlenül választottuk.
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 megtehetjük, hogy csak bizonyos éleket választhatunk ki véletlenül, a többi egyáltalán nem szerepelhet. (Gondoljunk Csermely Péter a Mindentudás Egyetemén korábban elhangzott előadására Hálózatok sejtjeinkben és körülöttünk címmel.)
Az eddigiekben láttuk, hogy a véletlen gráfok tulajdonságai is leírhatók, ám különböznek a szándékosan készített, nem véletlen gráfokéitól. Ezek után meglepő lehet az az állítás, hogy minden gráf bizonyos értelemben véletlen. Márpedig így is megfogalmazható Szemerédi Endre akadémikus 1970-es évekből származó híres tétele. Egy gráfról akkor mondjuk, hogy kupacosan véletlen, ha a pontjai egyforma kupacokba oszthatók úgy, hogy a 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 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 kimondásához pontosítani kellene, 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, mégis igen fontos az elmélet számára. Manapság is nagyon sok nehéz problémát oldanak meg a segítségével.
A gráfelmélet még sakkversenyek rendezéséhez is szükséges. A játékosok a pontok, az összekötések a játszmák. Tegyük fel, hogy sok versenyzővel akarunk körmérkőzést lebonyolítani. Azt szeretnénk, hogy mindennap mindenki játsszon valakivel, és néhány nap után előálljon az a helyzet, hogy mindenki mindenkivel éppen egyszer játszott. Ennek érdekében már régóta táblázatok segítségével rendezik a versenyeket. Nagy feltűnést keltett, amikor 1883-ban a nürnbergi torna kezdését el kellett halasztani, mert a táblázat készítője otthon felejtette a beosztást.
Most képzeljük el, hogy hat 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, oly módon, 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 három 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.
Térjünk át az igazi magyar játékról egy volt magyar játékra, a futballra! Mi van, ha 60 fiatal hasonlóan akarja eldönteni, hogy ki a legjobb futballista? Hatos csoportokban küzdenek, kapus nélkül kispályán, a legtöbb gólt rúgó nyer egy mérkőzésen. Meg lehet-e ezt szervezni a lehető legkevesebb teljes fordulóban úgy, hogy minden hatos csoport pontosan egyszer játsszon? Sylvester angol matematikus az 1850-es években úgy 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 az azóta sajnos autóbalesetben elhunyt Baranyai Zsolt. A matematikai probléma nem látszott sem túl fontosnak, sem túl nehéznek. Megoldotta, és csak később derült ki, hogy mindez lényegében Sylvester 120 éve megoldatlan sejtése volt, csak más formában.
A következőkben az előadó egy 1965-ben született eredményét, tételét mutatja be. A kedves olvasók már gyakorlottak lettek, így ezen a ponton csapatok és hasonlók helyett már beszélhetünk 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, ennél kevesebb nem. Válasszunk most 3 darab háromelemű halmazt! Mikor lesz az összes árnyékhalmaz száma a legkevesebb? Sejthető, hogy akkor, ha a halmazokat „közel” vesszük. Így már logikus, hogy ahhoz, hogy 9 árnyékhalmazt kapjunk, 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 sejthető, hogy minél „közelebb” kell őket venni. Rajzoljunk most másképpen. Számozzuk meg az elemeket, amelyekből a halmazokat csináljuk, az egyszerűség kedvéért vegyünk csak 5 elemet: 1, 2, 3, 4 és 5. 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. Gyanítható, hogy ez a legjobb elrendezés. Erre vonatkozik az úgynevezett Kruskal–Katona-tétel.
Végül szóljunk egy alkalmazásról. Katona Gyula Haraszti Attilával, Marsovszky Lászlóval, Csirmaz Lászlóval, Miklós Dezsővel és Nemetz Tiborral kidolgozott 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 technológia vagy a matematikai háttér ismerete nélkül is talán érzékelhető, hogy itt szintén hogyan kerül elő a halmazok árnyéka.
Az előadás a kombinatorika magyar vonatkozású eredményei közül válogatott a teljesség igénye nélkül. Reméljük, sikerült átadnunk valamit ebből az érdekes és izgalmas kutatási területből, és hogy az előadás nézői, olvasói között vannak olyan leendő matematikusok, akiknek eredményeit 50 év múlva hasonló előadás kereteiben fogják ismertetni.

A fenti szöveg a május 15-én elhangzott előadás rövidített változata.