Extremale Graphentheorie

Die extremale Graphentheorie untersucht, wie groß oder dicht ein Graph sein kann, ohne eine vorgeschriebene Unterstruktur zu enthalten, und identifiziert die extremalen Konfigurationen.

Definition

Die Untersuchung des maximalen oder minimalen Wertes eines Graphenparameters, wie der Anzahl der Kanten, unter einer strukturellen Einschränkung, wie dem Fehlen eines festen Untergraphen.

Scope

Dieses Thema konzentriert sich auf Probleme vom Turan-Typ – die maximale Anzahl von Kanten in einem Graphen ohne einen gegebenen Untergraphen – beginnend mit den Sätzen von Mantel und Turan und sich erstreckend bis zum Satz von Erdos-Stone, der die asymptotische extremale Dichte für jeden verbotenen Untergraphen bestimmt. Es führt das Zusammenspiel von Dichte, Struktur und der Szemeredi-Regularitätsmethode ein.

Core questions

• Was ist die maximale Anzahl von Kanten in einem Graphen mit n Knoten, der keine Kopie eines gegebenen Untergraphen enthält?
• Welche Graphen erreichen diese extremalen Schranken?
• Wie bestimmt die chromatische Zahl eines verbotenen Untergraphen die asymptotische Antwort?
• Wie reduzieren Regularitätsmethoden dichte Graphen auf eine begrenzte Struktur?

Key concepts

• Verbotene Untergraphen
• Turan-Graph
• Satz von Mantel
• Extremalzahl (Turan-Zahl)
• Satz von Erdos-Stone
• Szemeredi-Regularitätslemma

Key theories

Satz von Turan

Unter allen Graphen mit n Knoten ohne vollständigen Untergraphen mit r+1 Knoten hat der balancierte vollständige r-partite Graph die meisten Kanten, was Mantels dreiecksfreie Schranke verallgemeinert und die extremale Graphentheorie verankert.

Satz von Erdos-Stone

Für jeden festen verbotenen Untergraphen H wird die maximale Kantendichte eines H-freien Graphen asymptotisch durch die chromatische Zahl von H bestimmt, wodurch extremale Ergebnisse vom Turan-Typ vereinheitlicht werden.

Clinical relevance

Extremale Dichteergebnisse begrenzen die Struktur großer Netzwerke und Beschränkungssysteme, und die in diesem Bereich entwickelte Regularitätsmethode findet Anwendungen im Eigenschaftstesten (property testing), in der theoretischen Informatik und in der additiven Kombinatorik.

History

Mantels Schranke für dreiecksfreie Graphen von 1907 und Turans Verallgemeinerung von 1941 begründeten das Feld; die Erdos-Stone-Simonovits-Theorie und Szemeredis Regularitätslemma machten es zu einer zentralen Säule der modernen Kombinatorik.

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

Was ist ein Problem vom Turan-Typ?

Es fragt nach der größten Anzahl von Kanten, die ein Graph haben kann, während er einen festen Untergraphen vermeidet; das kanonische Beispiel ist die maximale Anzahl von Kanten in einem dreiecksfreien Graphen.

Wie hängt die extremale Graphentheorie mit der Ramsey-Theorie zusammen?

Beide untersuchen unvermeidbare Strukturen, aber die extremale Theorie legt einen verbotenen Untergraphen fest und maximiert die Kanten, während die Ramsey-Theorie eine monochromatische Struktur garantiert, sobald der Graph groß genug ist.