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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.