Lexikon der Mathematik: Erdős-Simonovits, Satz von
sagt aus, daß für r, s ∈ ℕ ein n0 ∈ ℕ existiert, so daß für n ≥ n0 der Graph
Dabei bezeichnet Tr(n − s + 1) den nach dem Satz von Turán eindeutig bestimmten kantenmaximalen Graphen der Ordnung n − s + 1, der keinen vollständigen Graphen Kr+1 der Ordnung r + 1 als Teilgraphen enthält.
Der Graph Ks−1 + Tr(n − s + 1) entsteht, indem man alle Ecken aus Tr(n − s + 1) mit allen Ecken eines vollständigen Graphen Ks−1 durch Kanten verbindet.
P. Erdős und M. Simonovits veröffentlichten diesen und eine Reihe ähnlicher Sätze in den Jahren 1967 und 1968.
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.