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