Lexikon der Mathematik: Szemeredi, Regularitätslemma von
sagt aus, daß für ϵ > 0 und l ∈ ℕ zwei Zahlen L, n0 ∈ ℕ so existieren, daß die Eckenmenge jedes GraphenG der Ordnung n ≥ n0 eine Partition E(G) = E0 ∪ E1 ∪ E2 ∪…∪ Ek besitzt, die folgende Bedingungen erfüllt:
Ein Paar nichtleerer disjunkter Eckenmengen (X, Y) in einem Graphen G heißt dabei ϵ-regulär, wenn
für alle Mengen X′ ⊆ X und Y′ ⊆ Y mit |X′ | ≥ ϵ|X| > 0 und |Y′ | ≥ ϵ|Y | > 0 gilt. Dabei ist
und k(X, Y) ist die Anzahl der Kanten in G mit einem Endpunkt in X und einem Endpunkt in Y.
E. Szemeredi bewies diese Aussage 1975. Das Regularitätslemma hat eine Reihe von Anwendungen in der extremalen Graphentheorie, und mit ihm wird oft die Existenz bestimmter Teilgraphen in Graphen nachgewiesen.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.