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!"
Videó ^|1}| : Erdős Pál-portré (részlet)
Forrás: zalafilms.com

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?

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 (3. ábra).

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 (4. ábra). 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 (5. ábra).

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)
Animáció ^|2}| : Erdős Pál társszerzői hálózata

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 (7. ábra). 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.

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 (10. ábra) 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 (11. ábra).

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.

Animáció ^|3}| : Sakkjátszmák 6 játékossal 5 fordulóban

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:

Animáció ^|4}| : Sakkjátszmák kiosztása helytelenül

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.

Animáció ^|5}| : Három fős csapatok alakítása hat főből, 10 fordulóban

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.

Videó ^|6}| : filmrészlet Baranyai Zsoltról 

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 (12. ábra). 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.

Animáció ^|7}| : Háromelemű halmaz árnyékhalmazai

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
Animáció ^|8}| : Két háromelemű halmaz árnyékhalmazai - amikor a halmazoknak nincs közös elemük

és 5 is.

Animáció ^|9}| : Két háromelemű halmaz árnyékhalmazai - amikor a halmazok "közel vannak egymáshoz"

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:

Animáció ^|10}| : Három háromelemű halmaz árnyékhalmazai - amikor 7 árnyékhalmaz van;

ez pedig csak 6-ot:
Animáció ^|11}| : Három háromelemű halmaz árnyékhalmazai - amikor 6 árnyékhalmaz van

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).

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.

Videó ^|12}| : Digitális vízjel (részlet a Deltából)

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...