Direkt zum Inhalt

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

sagt aus, daß für ϵ > 0 und r ∈ ℕ ein n0 ∈ ℕ existiert, so daß jeder Graph der Ordnung nn0 mit mindestens \begin{eqnarray}\left(1-\frac{1}{r}+\varepsilon \right)\left(\begin{array}{c}n\\ 2\end{array}\right)\end{eqnarray}

Kanten einen Graphen Kr+1(t) mit t → ∞ für n → ∞ als Teilgraphen enthält.

Dabei ist Kr+1(t) der vollständige (r + 1)-partite Graph mit t Ecken in jeder Partitionsmenge.

P. Erdős und A.H. Stone bewiesen diesen zentralen Satz der sog. extremalen Graphentheorie bereits 1946.

B. Bollobás und P. Erdős verschärften die Aussage 1973, indem sie zeigten, daß obiges t für n → ∞ mindestens wie c·log n für ein konstantes c wächst.

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