Satz von Babai – Wikipedia
Der Satz von Babai ist ein mathematischer Lehrsatz, welcher im Übergangsfeld zwischen den Teilgebieten Graphentheorie und Gruppentheorie angesiedelt ist. Er geht auf eine Veröffentlichung des ungarischen Mathematikers László Babai aus dem Jahre 1974 zurück. Der Satz ist verwandt mit dem Satz von Frucht, denn er behandelt eine spezielle Problemstellung im Zusammenhang mit der Frage der Darstellbarkeit endlicher Gruppen als Automorphismengruppen schlichter Graphen. Er zieht als Folgerung nach sich, dass eine von Pál Turán im Jahre 1969 gestellte Frage, ob nämlich jede endliche Gruppe als Automorphismengruppe eines ebenen Graphen darstellbar ist, verneinend zu beantworten ist.[1]
Formulierung des Satzes
[Bearbeiten | Quelltext bearbeiten]Der Satz lässt sich angeben wie folgt:[2]
- Sei eine Klasse schlichter Graphen mit den folgenden beiden Eigenschaften:
- (1) enthält mit einem schlichten Graphen stets auch jedes graphenhomomorphe Bild eines jeden Minors .
- (2) Zu jeder endlichen Gruppe gebe es in einen (möglicherweise unendlichen) schlichten Graphen , dessen Automorphismengruppe gruppenisomorph zu ist.
- Dann gilt:
- Die Graphenklasse enthält alle endlichen schlichten Graphen.
Quellen und Literatur
[Bearbeiten | Quelltext bearbeiten]- Rudolf Halin: Graphentheorie. 2., überarbeitete und erweiterte Auflage. Wissenschaftliche Buchgesellschaft, Darmstadt 1989, ISBN 3-534-10140-5 (MR1068314).
- László Babai: Automorphism groups of graphs and edge-contraction. In: Discrete Mathematics. Band 8, 1974, S. 13–20 (sciencedirect.com). MR0332554