Satz von Babai

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

Der Satz lässt sich angeben wie folgt:^[2]

Sei ${\displaystyle {\mathcal {G}}}$ eine Klasse schlichter Graphen mit den folgenden beiden Eigenschaften:

(1) ${\displaystyle {\mathcal {G}}}$ enthält mit einem schlichten Graphen ${\displaystyle G\in {\mathcal {G}}}$ stets auch jedes graphenhomomorphe Bild eines jeden Minors ${\displaystyle G^{*}\preccurlyeq G}$ .

(2) Zu jeder endlichen Gruppe ${\displaystyle \Gamma }$ gebe es in ${\displaystyle {\mathcal {G}}}$ einen (möglicherweise unendlichen) schlichten Graphen ${\displaystyle G_{\Gamma }}$, dessen Automorphismengruppe ${\displaystyle \mathrm {Aut} (G_{\Gamma })}$ gruppenisomorph zu ${\displaystyle \Gamma }$ ist.

Dann gilt:

Die Graphenklasse ${\displaystyle {\mathcal {G}}}$ enthält alle endlichen schlichten Graphen.

Quellen und Literatur

• 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

Siehe auch

• Satz von Frucht