Direkt zum Inhalt

Lexikon der Mathematik: Erdős-Simonovits, Satz von

sagt aus, daß für r, s ∈ ℕ ein n0 ∈ ℕ existiert, so daß für nn0 der Graph \begin{eqnarray}G={K}_{s-1}+{T}_{r}(n-s+1)\end{eqnarray} der eindeutige kantenmaximale Graph der Ordnung n ist, der keine s disjunkten vollständigen Graphen Kr+1 der Ordnung r + 1 als Teilgraphen enthält.

Dabei bezeichnet Tr(ns + 1) den nach dem Satz von Turán eindeutig bestimmten kantenmaximalen Graphen der Ordnung ns + 1, der keinen vollständigen Graphen Kr+1 der Ordnung r + 1 als Teilgraphen enthält.

Der Graph Ks−1 + Tr(ns + 1) entsteht, indem man alle Ecken aus Tr(ns + 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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos