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
A kombinatorika a 20. században gyors fejlődésnek indult, jelentős részben magyar matematikusoknak köszönhetően. A század derekán született eredmények többnyire játékos, fejtörő jellegű feladatok voltak. Megoldásuk gyakorlati haszonnal ugyan nem kecsegtetett, de nehézségük komoly szakmai kihívást jelentett. Amikor azonban a számítógépek megjelentek, a kombinatorika egy csapásra kulcsfontosságú területté vált, hiszen a számítástudomány egyik alapja éppen ez a tudományág.

II. Mennyi Madonna Latabár-száma?
A matematikusok a maguk szórakoztatására megalkottak egy gráfot, melyben a pontok matematikusoknak felelnek meg, két pont (két matematikus) között pedig akkor van él, ha az illetőknek van közös tudományos cikkük. Ennek alapján meghatározható az ún. Erdős-szám, ami azt jelenti, hogy ebben a gráfban hány lépésen (ponton) keresztül vezet út Erdős Páltól az illetőig. Hasonlóképpen, az amerikai fiatalok körében népszerű Kevin Bacon-játékban a pontok színészek, és kettő pont akkor van összekötve, ha játszottak egy közös filmben. Ez alapján fel lehet tenni például azt a kérdést: milyen messze van egymástól Latabár Kálmán és Madonna?

III. Véletlen gráfok
Erdős Pál és Rényi Alfréd az 1960-as években dolgozták ki a véletlen gráfok elméletét. Véletlen gráfhoz úgy juthatunk, hogy a pontok között kiválasztunk egy élet véletlenül, az összes élből egyforma valószínűséggel. Ezután veszünk egy újabbat a maradék élek közül, ismét egyforma valószínűséggel és így tovább. Az elmélet akkor válik izgalmassá, amikor a pontok száma elegendően nagy. Ha ez a szám egymilliárdnál is nagyobb, akkor tetszőleges gráfban található valamilyen jól használható rendszer: az ilyen nagy gráfokban kijelölhetők olyan ponthalmazok ("kupacok"), melyek között az élek úgy viselkednek, mintha véletlenek lennének. Ez a Szemerédi-tétel, amelynek ugyan még nincsenek gyakorlati alkalmazásai, de igen fontos az elmélet számára.

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. 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 pontosan egyszer játszott. Csakhogy nem olyan nyilvánvaló, hogy ezt meg lehet csinálni, és ha igen, hogyan. Emlékezetes eset történt 1883-ban, amikor el kellett halasztani a Nürnbergi Torna kezdését, mert a verseny menetét leíró táblázatot készítője otthon felejtette.

V. A halmazok "árnyékvilága"
Az előadás utolsó részében megismerkedünk a halmazokon értelmezett árnyékhalmazokkal, megtudjuk hogy néz ki egy halmaz árnyéka, majd megfogalmazzuk a hatvanas években született Kruskal-Katona-tételt.

Tovább