The lower bound of diameter of Alternating groups
DOI:
https://doi.org/10.17721/1812-5409.2021/4.1Keywords:
Cayley graph, diameter of graph, system of generators, alternating groupAbstract
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
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
