Lovász László

Hova nőnek a nagy hálózatok?

IV. A Szemerédi-féle regularitási lemma

Térjünk vissza a nagy hálózatokra. Hogyan tudnánk a szerkezetüket megérteni, kevés adattal leírni? Ehhez érdemes egy ábrázolásmóddal megismerkedni. A rajznál néha többet mond a 15. ábrán látható összekötöttségi táblázat (és természetesen számításokban jobban használható). Hogy még jobban látszódjon a gráf szerkezete, helyettesítsük az 1-est fekete, a 0-t fehér négyzettel. Így a 16. ábrán látható, keresztrejtvényre emlékeztető rajzot kapunk.

15. ábra

16. ábra

Ha ezzel az ábrázolási technikával egy olyan Erdős-Rényi-féle véletlen gráfot ábrázolunk, melyben a csúcspárok fele van összekötve, akkor "messziről nézve" az ábra egyenletesen szürkének fog látszani (17. ábra ). De vigyázzunk! Hiszen "messziről" a 18. ábrán bemutatott sakktábla-szerű elrendezés is egyenletesen szürkének látszik, ha nagyon sok sora van. Ha azonban itt a sorokat és oszlopokat átrendezzük úgy, hogy előrehozzuk a párosakat, akkor a 18. ábra jobboldalán látható sokkal szabályosabb, igen egyszerű struktúrát kapjuk. Ezzel szemben egy véletlen gráf ábráját akárhogyan rendeznénk át, mindenképpen egyenletesen szürke volna.

17. ábra

18. ábra

Itt az ideje, hogy bemutassuk a 20. századi magyar matematika egyik legnagyobb hatású eredményét, Szemerédi Endre (19. ábra) regularitási lemmáját. A 20. ábra bal felső sarkában látható gráfnak nem látszik különösebb struktúrája. Azonban a csúcsait alkalmasan átrendezve a jobb felső sarokban már azt látjuk, hogy az ábra négy különböző sűrűségű területre oszlik. Ezeken a területeken belül azonban már további struktúra nincs, ezek a részek már véletlenszerűek. A Szemerédi-lemma éppen ezt fogalmazza meg: minden gráf felbontható korlátos számú részre (ezek száma csak a hibahatártól függ, nem függ a gráftól) úgy, hogy a megfelelő kisebb négyzeteken a keresztrejtvény-ábra (kis hibával) véletlenszerű, más-más sűrűséggel. Ha ezeket a sűrűségeket ismerjük, a gráf sok fontos tulajdonságát meg tudjuk mondani.

19. ábra

20. ábra