The lower bound of diameter of Alternating groups

Authors

  • M. Olshevskyi Taras Shevchenko National University of Kyiv

DOI:

https://doi.org/10.17721/1812-5409.2021/4.1

Keywords:

Cayley graph, diameter of graph, system of generators, alternating group

Abstract

In this paper we consider a specific case of the diameter search problem for finite groups, thecase where the system of generators is fixed. This problem is well-known and can be formulated in the following way: find the diameter of a group over its system of generators. The diameter of the corresponding Cayley graph is the diameter of a group over its specific system of generators.

The main object of the research is the alternating group with the system of generators consisting of cycles having length three and the form (1,2,k). This system of generators is a classical irreducible system of generators of the alternating group. It is introduced the property of even permutations to be balanced. We consider the set of balanced permutations and permutations close enough to balanced and find minimum decompositions of them over defined system of generators.

The main result of the paper is the lower bound of the diameter of Alternating group over con-sidered system of generators. The estimation is achieved using minimal decompositions of balanced permutations.

Pages of the article in the issue: 11 - 22

Language of the article: English

References

S. AKERS, B. KRISHNAMURTHY and D. HAREL (1994) The Star Graph: An At-tractive Alternative to the n-Cube. In International Conference on Parallel Processing. Raleigh, North Carolina, Monday 15th to Friday 19th August 1994. North Carolina State University.

L. BABAI and A. SERESS (1992) On the diameter of permutation groups. European Journal of Combinatorics. 13 (4). p.231-243.

E. BREUILLARD, B. GREEN and T. TAO (2010) Approximate subgroups of linear groups [Online] Available from: https://arxiv.org/abs/1005.1881 m. [Accessed: 11th May 2010].

L. PYBER and E. SZABO (2011) Growth in finite simple groups of Lie type of bounded rank. [Online] Available from: https://arxiv.org/abs/1005.1858 m. [Accessed: 8th April 2011].

H. HELFHOTT and A. SERESS (2014) On the diameter of permutation groups. Annals of Mathematics. 199 (2). p.611-658.

J. BAJPAI, D. DONA and H. HELFGOTT (2021) Growth estimates and diameter boundsfor classical Chevalley groups. [Online] Available from: https://arxiv.org/abs/2110.02942 m. [Accessed: 6th October 2021].

S. EVEN and O. GOLDREICH (1981) The minimum-length generator sequence problem is NP-hard. Journal of Algorithms. 2 (3). p.311-313.

M. OLSHEVSKYI (2021) Diameter search algorithms for directed Cayley graphs. Mohyla Mathematical Journal. (4). p.614-625.

M. OLSHEVSKYI (2021) Metric properties of Cayley graphs of Alternating groups. Carpathian Mathematical Publications. 13 (2). p.545-581.

Downloads

Published

2021-12-21

How to Cite

Olshevskyi, M. (2021). The lower bound of diameter of Alternating groups. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences, (4), 11–22. https://doi.org/10.17721/1812-5409.2021/4.1

Issue

Section

Algebra, Geometry and Probability Theory