Publish on 13th November 2019
Category: Birds
0

On Representations of AbstractGroupsasAutomorphismGroups of Graphs.ArchilKipianiIv.JavakhishviliTbilisi State UniversityWinter School 2011HejniceThis research was supported by Rustaveli NSFGrant-GNSF/ST 09_144_3-105

s

Problem(D.König,1936).

Whether for any abstract group thereexists a graph whoseautomorphismsgroup is isomorphic to the given abstractgroup?Thisproblem has been solved positively, byFrucht(1938) andSabidussi,for finite and forinfinitegroups respectively.

Theorem(G.Sabidussi,1960).

LetGbe any group, and letκbe a cardinal.Then there exists a connected graphXsuchthat (i)Aut(X)≅G,and(ii) Xhas at leastκvertices.Ingeneral, similar problems of representation ofthegroups, requires the consideration of some set,whosecardinality is strictly greater than thecardinalityof the original group.

Note

The graph ofSabidussihas the cardinalitystrictly greater than the cardinality of aninitial group.

Question

Is thereagraphHGof cardinalityGsuch thatAut(HG) ≈ G,for any infinite groupG?

Is there a graphHGof cardinalityGsuchthatAut(HG)≅G,for any infinite groupGThesimilarquestion concerning groups representations, byautomorphismgroups of abinaryrelation of the same power, was posed byStoller.

Problem(G.Stoller1976)

Let(G,○)is an infinite group. Is there a binaryrelationBonG, such that theAut(G,B)isisomorphic to the group(G,○)?A positive solutionoftheStoller’squestion wasgiven in the following theorem.

Theorem(A.B.Kharazishvili1981)

Ifis any infinite cardinal number, andGis a group whichG, then there exista setEGof cardinalityand a binaryrelationBGon the setEG, such that thegroup of allautomorphismsof the structure(EG,BG)and the groupGare isomorphic.

Letbe any infinite cardinal andGbe anygroup withG.Then there exist a family{Hi:iI}such that, for eachdifferenti,jI:Hiis connected graph;non( Hi≅Hj);Hi=;I=2;Aut( Hi)≅G.Thisversion ofsolutionofKönig'sproblem has closeconnectionswith other combinatorialquestions:

Problem(S.Ulam,1960)

Can we find, for every natural numbern,abinary relationBon a infinite setEsuchthat the structure(E , B)has preciselynautomorphisms?Solved byKharazishvili,Kipiani,withindicatingtheroleof the Axiom ofChois.

Problem(B.Jonsson, 1972)

What is the cardinality of the set of allpairwisenon isomorphic undirected graphs,of the order, for each infinite cardinal?(Solvedby C.M. Bang).Fromthe above theorem, it follows the solutionofthestronger versions of each of the mentionedproblems.

Remark

It is impossible to represent all infinite groupsasautomorphismgroups of trees.

Problem1.

Clearly, some infinite groups can berepresented asautomorphismgroups of agraph whose cardinality is less than thecardinality of the initial group. Give acharacterization of such groups.

Problem 2.

Letbe an infinite cardinal. Give acharacterization of all groups of cardinality2which admit representation as theautomorphismsgroup of a graph ofcardinality.

s

Problem 3.

Characterize all groups of cardinality ofthe continuum, which can be represented asautomorphismgroups of some countablegraph.

Thank you for your attention !

0

Embed

Upload

Satauri an momzsenebeli