On the isomorphism problem for cyclic combinatorial objects
type: Item
instance of: scholarly article
title: On the isomorphism problem for cyclic combinatorial objects
zbMATH Open document ID: 0938.05005
DOI: 10.1016/S0012-365X(99)90119-X
published in: Discrete Mathematics
publication date: 1999-08-09T00:00:00Z
review text: As usual, we denote by \(S(X)\) the group of all permutations of a finite set \(X\). By \(\text{Rel}(X)\) we mean the set of all relations over \(X\). The finite subsets of \(\text{Rel}(X)\) are called combinatorial objects over \(X\). We write \((H;X)\) when a subgroup \(H\) of \(S(X)\) is considered as a permutation group of \(X\), and we denote by \(\text{Obj}(H;X)\) the set of all combinatorial objects which are left invariant by \((H;X)\). Let \(S\) be a subset and \(H\) a subgroup of \(S(X)\). \({\mathcal R}\) be an element of \(\text{Obj}(H;X)\). We say that \(S\) is a solving set for \({\mathcal R}\) if the following two assertions are equivalent for any \({\mathcal T}\in \text{Obj}(H;X)\): (i) There is an element of \(S(X)\) which transforms \({\mathcal R}\) into \({\mathcal T}\). (ii) There is an element of \(S\) which transforms \({\mathcal R}\) into \({\mathcal T}\). A partial order \(\prec^{\sqcup}_H\) is introduced (in an appropriate manner) on the set of all permutation groups of \(X\) containing a regular cyclic subgroup \((H;X)\). The main results of the paper are the following assertions. If \((H;X)\) is a regular cyclic group and \({\mathcal R}\in \text{Obj}(H;X)\), then the minimum cardinality of the solving sets for \({\mathcal R}\) is equal to the number of conjugacy classes of \(X\)-cycles in the automorphism group of \({\mathcal R}\), and it does not exceed \(\varphi(|X|)\) (where \(\varphi\) is the Euler function). If \((G;H)\) contains a regular cyclic subgroup \((H;X)\) and \((G;X)\) is \(\prec^{\sqcup}_H\)-minimal, then \(G\) is solvable. A further statement shows that, if the divisibility \(p|q-1\) is false for any choice of two prime divisors \(p\), \(q\) of \(|X|\), then the isomorphism problem for cyclic combinatorial objects may be reduced to the one on prime power numbers of elements. The proofs are involved group-theoretical considerations, using the classification theory of finite simple groups.
reviewed by: A. Ádám
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 20B99
zbMATH DE Number: 1322040
zbMATH Keywords: combinatorial objects
zbMATH Keywords: permutation group
zbMATH Keywords: solving set
zbMATH Keywords: partial order
zbMATH Keywords: regular cyclic group
zbMATH Keywords: isomorphism problem
author: Mikhail Muzychuk
MaRDI profile type: Publication
cites work: Isomorphism of circulant graphs and digraphs
cites work: Isomorphism problem for a class of point-symmetric structures
cites work: Q4189301
cites work: Isomorphisms of Cayley graphs. II
cites work: Sur les systèmes cycliques de triples de Steiner différents pour \(N\) premier (ou puissance de nombre premier) de la forme \(6n+1\). II--III
cites work: Q3726133
cites work: Isomorphisms of cyclic combinatorial objects
cites work: Polynomial isomorphisms of combinatorial objects
cites work: Isomorphism problem for a special class of graphs
cites work: Graphs with circulant adjacency matrices
cites work: On finite simple groups of characteristic 2 type
cites work: The equivalence of two cyclic objects on \(pq\) elements
cites work: Multipliers and generalized multipliers of cyclic objects and cyclic codes
cites work: Q5648532
cites work: Q3724529
cites work: Q3889083
cites work: Q3205264
cites work: Ádám's conjecture is true in the square-free case
cites work: Corrigendum to: On Ádám's conjecture for circulant graphs
cites work: Isomorphism problem for relational structures with a cyclic automorphism
cites work: Q3791159
cites work: Q5512231
full work available at URL: s0012-365x(99)90119-x
OpenAlex ID: W4236779693
description: scientific article; zbMATH DE number 1322040