How long does it take to generate a group?

DOI10.1016/S0021-8693(02)00671-3MaRDI QIDQ1868919zbMATH OpenFDO

Authors Benjamin Klopsch, Vsevolod F. Lev

Publication date 28 April 2003

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.2908

zbMATH Keywords

generating setsfinite Abelian groupsdiameters of Cayley graphsdiameters of finite groups

Mathematics Subject Classification ID

Arithmetic and combinatorial problems involving abstract finite groups (20D60) Generators, relations, and presentations of groups (20F05) Finite abelian groups (20K01)

Abstract: The diameter of a finite group $G$ with respect to a generating set $A$ is the smallest non-negative integer $n$ such that every element of $G$ can be written as a product of at most $n$ elements of $Acup{A}^{-1}$. We denote this invariant by $dia{m}_A(G)$. It can be interpreted as the diameter of the Cayley graph induced by $A$ on $G$ and arises, for instance, in the context of efficient communication networks. In this paper we study the diameters of a finite abelian group $G$ with respect to its various generating sets $A$. We determine the maximum possible value of $dia{m}_A(G)$ and classify all generating sets for which this maximum value is attained. Also, we determine the maximum possible cardinality of $A$ subject to the condition that $dia{m}_A(G)$ is "not too small". Connections with caps, sum-free sets, and quasi-perfect codes are discussed.

Recommendations

• Generating abelian groups by addition only
• Diameter of a direct power of a finite group
• Some results on diameters of Cayley graphs
• Finite groups of uniform logarithmic diameter.
• Small-diameter Cayley graphs for finite simple groups

Cites work

• scientific article; zbMATH DE number 1229718 (Why is no real title available?)
• scientific article; zbMATH DE number 1315277 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 3207391 (Why is no real title available?)
• Abschätzung der asymptotischen Dichte von Summenmengen
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Generating binary spaces.
• On Bases for $\sigma$-Finite Groups.
• On the spectrum of the values \(k\) for which a complete \(k\)-cap in \(PG(n,q)\) exists
• Quasiperfect linear binary codes with distance 4 and complete caps in projective geometry
• Subset sums in binary spaces
• Sum-free sets in vector spaces over \(GF(2)\)

Cited in

(12)

• Large sum-free sets in \(\mathbb{Z}_5^n\)
• Factoring formal maps into reversible or involutive factors.
• Generating binary spaces.
• Direct and inverse theorems on signed sumsets of integers
• Three questions of Bertram on locally maximal sum-free sets
• Generating abelian groups by addition only
• Conjugation diameter of the symmetric groups
• How long does it take for all users in a social network to choose their communities?
• The minimum size of signed sumsets
• On the minimum size of signed sumsets in elementary abelian groups
• Geometric group theory and arithmetic diameter
• Direct and inverse problems for restricted signed sumsets in integers

This page was built for publication: How long does it take to generate a group?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1868919)