Extremal Density for Sparse Minors and Subdivisions

Das Kapitel vertieft sich in das Problem der Bestimmung der durchschnittlichen Gradbedingungen, die erforderlich sind, um einen Graphen H als Neben- oder Unterteilung in einen anderen Graphen G zu erzwingen. Es beginnt mit der Überprüfung der klassischen Theorie extremer Graphen und des Erdős-Stein-Simonovits-Theorems. Das Hauptaugenmerk liegt auf den durchschnittlichen Studienbedingungen für Minderjährige, wobei ein besonderer Schwerpunkt auf zweiseitigen Grafiken liegt. Der Autor präsentiert ein neues Ergebnis, das zeigt, dass eine notwendige Grenze bereits für eine natürliche Klasse spärlicher zweiseitiger Graphen ausreicht. Dieses Ergebnis hat erhebliche Auswirkungen auf das Verständnis des durchschnittlichen Grades, der erforderlich ist, um bestimmte spärliche Graphen als Minderjährige zu zwingen, einschließlich Gitter und ebene Graphen. Das Kapitel behandelt auch die Anwendung dieser Ergebnisse auf andere Graphenklassen, wie etwa kleinere geschlossene Familien und Klassen polynmischer Expansion. Der Beweis nutzt sowohl Pseudorandominität aus Szemerédis Regelmäßigkeitslelemma als auch Erweiterungen für spärliche Grafiken, wobei ein besonderer Schwerpunkt auf robusten sublinearen Expandern liegt. Das Kapitel schließt mit der Hervorhebung der Bedeutung dieser Ergebnisse im breiteren Kontext der Graphentheorie und ihrer potenziellen Anwendung in verschiedenen Bereichen.