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.
Schreiben Sie uns!