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

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

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Rudolf Halin: Graphentheorie. 1989, S. 199ff, 207, 209
  2. Halin, op. cit., S. 209–213