Representation of Abstract Groups through Graphs
Explore the representation of abstract groups as automorphism groups of graphs, touching on topics such as the existence of graphs whose automorphism groups are isomorphic to given abstract groups, the cardinality of connected graphs satisfying specific properties, and questions regarding the cardinality and automorphism groups of graphs in relation to infinite groups and binary relations. Delve into theorems, problems, and past research findings in this intriguing area of study.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
On Representations of Abstract Groups asAutomorphism Groups of Graphs. Archil Kipiani Iv. Javakhishvili Tbilisi State University Winter School 2011 Hejnice This research was supported by Rustaveli NSF Grant-GNSF/ST 09_144_3-105
Terminology : Under the term graph we mean an undirected, finite or infinite, graph; Tree is a acyclic connected graph; The symbol denotes an isomorphism relation, between algebraic structures.
Problem (D.Knig,1936). Whether for any abstract group there exists a graph whose automorphisms group is isomorphic to the given abstract group? s This problem has been solved positively, by Frucht (1938) and Sabidussi, for finite and for infinite groups respectively.
Theorem (G.Sabidussi,1960). Let G be any group, and let be a cardinal. Then there exists a connected graph X such that (i) Aut(X) G, and (ii) X has at least vertices. In general, similar problems of representation of the groups, requires the consideration of some set, whose cardinality is strictly greater than the cardinality of the original group.
Note The graph of Sabidussi has the cardinality strictly greater than the cardinality of an initial group.
Question Is there a graph HGof cardinality G such that Aut (HG) G, for any infinite group G Is there a graph HGof cardinality G such that Aut (HG) G, for any infinite group G? The similar question concerning groups representations, by automorphism groups of a binary relation of the same power, was posed by Stoller.
Problem(G.Stoller 1976) Let (G, ) is an infinite group. Is there a binary relation B on G, such that the Aut(G,B) is isomorphic to the group (G, )? A positive solution of the Stoller s question was given in the following theorem.
Theorem(A.B.Kharazishvili 1981) If is any infinite cardinal number, and G is a group which G , then there exist a set EG of cardinality and a binary relation BG on the set EG , such that the group of all automorphisms of the structure (EG ,BG) and the group G are isomorphic.
Theorem Let be any infinite cardinal and G be any group with G . Then there exist a family {H i :i I}such that, for eachdifferent i,j I: H iis connected graph; non ( H i H j ); H i = ; I =2 ; Aut ( H i ) G. This version of solution of K nig's problem has close connections with other combinatorial questions:
Problem(S.Ulam,1960) Can we find, for every natural number n, a binary relation B on a infinite set E such that the structure (E , B) has precisely n automorphisms? Solved by Kharazishvili,Kipiani, with indicating the role of the Axiom of Chois.
Problem (B.Jonsson, 1972) What is the cardinality of the set of all pairwise non isomorphic undirected graphs, of the order , for each infinite cardinal ? (Solved by C.M. Bang). From the above theorem, it follows the solution of the stronger versions of each of the mentioned problems.
Remark It is impossible to represent all infinite groups as automorphism groups of trees.
Problem 1. Clearly, some infinite groups can be represented as automorphism groups of a graph whose cardinality is less than the cardinality of the initial group. Give a characterization of such groups.
Problem 2. Let be an infinite cardinal. Give a characterization of all groups of cardinality 2 which admit representation as the automorphisms group of a graph of cardinality .
Problem 3. Characterize all groups of cardinality of the continuum, which can be represented as automorphism groups of some countable graph. s
