Metric properties of Cayley graphs of alternating groups

Authors

  • M.S. Olshevskyi Taras Shevchenko National University, 64/13 Volodymyrska str., 01601, Kyiv, Ukraine
https://doi.org/10.15330/cmp.13.2.545-581

Keywords:

Cayley graph, graph diameter, system of generators, alternating group
Published online: 2021-11-19

Abstract

A well known diameter search problem for finite groups with respect to its systems of generators is considered. The problem can be formulated as follows: find the diameter of a group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph.

It is considered alternating groups with classic irreducible system of generators consisting of cycles with length three of the form $(1,2,k)$. The main part of the paper concentrates on analysis how even permutations decompose with respect to this system of generators. The rules for moving generators from permutation's decomposition from left to right and from right to left are introduced. These rules give rise for transformations of decompositions, that do not increase their lengths. They are applied for removing fixed points of a permutation, that were included in its decomposition. Based on this rule the stability of system of generators is proved. The strict growing property of the system of generators is also proved, as the corollary of transformation rules and the stability property.

It is considered homogeneous theory, that was introduced in the previous author's paper. For the series of alternating groups with systems of generators mentioned above it is shown that this series is uniform and homogeneous. It makes possible to apply the homogeneous down search algorithm to compute the diameter. This algorithm is applied and exact values of diameters for alternating groups of degree up to 43 are computed.

Article metrics
How to Cite
(1)
Olshevskyi, M. Metric Properties of Cayley Graphs of Alternating Groups. Carpathian Math. Publ. 2021, 13, 545-581.