Babai's theorem

The set of Babai is a mathematical theorem which in the transition field between the sub-regions graph theory and group theory is located. It goes back to a publication by the Hungarian mathematician László Babai in 1974. The theorem is related to the theorem of Frucht , because it deals with a special problem in connection with the question of the representability of finite groups as automorphism groups of simple graphs . It implies that a question posed by Pál Turán in 1969, namely whether every finite group can be represented as an automorphism group of a plane graph , has to be answered in the negative.

Formulation of the sentence

The sentence can be stated as follows:

Let be a class of simple graphs with the following two properties: ${\displaystyle {\mathcal {G}}}$

(1) contains a directed graph always also each graphenhomomorphe image of each Minors . ${\displaystyle {\mathcal {G}}}$ ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle G^{*}\preccurlyeq G}$

(2) For every finite group there is a (possibly infinite ) simple graph whose automorphism group is group isomorphic to . ${\displaystyle \Gamma }$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle G_{\Gamma }}$ ${\displaystyle \mathrm {Aut} (G_{\Gamma })}$ ${\displaystyle \Gamma }$

Then:

The graph class contains all finite simple graphs. ${\displaystyle {\mathcal {G}}}$

Sources and literature

• Rudolf Halin : Graph Theory . 2nd, revised and expanded edition. Scientific Book Society , Darmstadt 1989, ISBN 3-534-10140-5 . MR1068314
• László Babai: Automorphism groups of graphs and edge-contraction . In: Discrete Mathematics . tape 8 , 1974, p. 13-20 ( sciencedirect.com ). MR0332554

See also

• Set of fruit

Individual evidence

1. ^ Rudolf Halin: Graph theory. 1989, pp. 199ff, 207, 209
2. ↑ Halin, op. Cit., Pp. 209-213