Katona Gyula

Hogyan lett "magyar matematika" a kombinatorika?

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

10. ábra

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.