Satz von Babai

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Rudolf Halin: Graphentheorie. 1989, S. 199ff, 207, 209
  2. Halin, op. cit., S. 209–213