KöNIG'S PROBLEM FOR ABELIAN PERMUTATION GROUPS

König's problem for permutation groups concerns the following question: Given a permutation group P = (P, X) acting on a finite set X, is there a graph G=(G, X) with the set of vertices X, such its automorphisms are precisely permutations in P? König's problem is to find a necessary and sufficient conditions for a permutation group P to be the automorphism groups of some graph.

There exist permutation groups that are not the automorphism groups of any graph (for example, alternating groups or groups generated by a single cyclic permutation). So far, this version of König’s problem (known also as the concrete version) has been solved only for regular permutation groups, cyclic permutation groups (generated by a single permutation), and partially, for abelian permutation groups.

In this talk we demonstrate however that the result by Zelikovskij [3] concerning König's problem for abelian permutation groups, reported in a recent survey [2], is false. We argue that a more natural setting for this problem is that concerning the automorphism groups of edge-colored graphs. Our main result, based on techniques applied in [1], provides a characterization of those abelian permutation groups that are the automorphism groups of edge-colored graphs and shows, in addition, that each such group can be represented by an edge-colored graph using no more than 4 colors.

References


[1] M. Grech, A. Kisielewicz, Symmetry groups of boolean functions, European J. Combin. 40 (2014) 1-10.

[2] J. Morris, Automorphism Groups of Circulant Graphs - a Survey, in: Bondy A., Fonlupt J., Fouquet JL., Fournier JC., Ramrez Alfonsn J.L. (eds) Graph Theory in Paris. Trends in Mathematics. Birkhuser Basel 2006, pp. 311-325.

[3] A. Z. Zelikovskij, Konigs problem for Abelian permutation groups, Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk 5 (1989), 34-39.