On the isomorphism problem for cyclic combinatorial objects

DOI10.1016/S0012-365X(99)90119-XMaRDI QIDQ1292864zbMATH OpenOpenAlexFDO

Authors Mikhail Muzychuk

Publication date 9 August 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)90119-x

zbMATH Keywords

combinatorial objectsisomorphism problempartial orderpermutation groupregular cyclic groupsolving set

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Permutation groups (20B99)

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.

Recommendations

• Polynomial isomorphisms of combinatorial objects
• Isomorphisms of cyclic combinatorial objects
• Finding a cycle base of a permutation group in polynomial time
• Testing isomorphism of circulant objects in polynomial time
• Publication:5752581

Cites work

• Corrigendum to: On Ádám's conjecture for circulant graphs
• Graphs with circulant adjacency matrices
• scientific article; zbMATH DE number 3646933 (Why is no real title available?)
• scientific article; zbMATH DE number 3955189 (Why is no real title available?)
• scientific article; zbMATH DE number 3957121 (Why is no real title available?)
• scientific article; zbMATH DE number 4055624 (Why is no real title available?)
• scientific article; zbMATH DE number 3695231 (Why is no real title available?)
• scientific article; zbMATH DE number 3627216 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 3377465 (Why is no real title available?)
• Isomorphism of circulant graphs and digraphs
• Isomorphism problem for a class of point-symmetric structures
• Isomorphism problem for a special class of graphs
• Isomorphism problem for relational structures with a cyclic automorphism
• Isomorphisms of Cayley graphs. II
• Isomorphisms of cyclic combinatorial objects
• Multipliers and generalized multipliers of cyclic objects and cyclic codes
• On finite simple groups of characteristic 2 type
• Polynomial isomorphisms of combinatorial objects
• 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
• The equivalence of two cyclic objects on pq elements
• Ádám's conjecture is true in the square-free case

Cited in

(40)

• Permutation group approach to association schemes
• On the isomorphism problem for Cayley graphs of abelian groups whose Sylow subgroups are elementary abelian or cyclic
• On isomorphisms of abelian Cayley objects of certain orders
• On the Cayley isomorphism problem for ternary relational structures
• The isomorphism problem for cyclic blocks and their source algebras
• Testing isomorphism of circulant objects in polynomial time
• Cyclic groups are CI-groups for balanced configurations
• The isomorphism problem for rose window graphs
• On Cayley representations of central Cayley graphs over almost simple groups
• Recognizing and testing isomorphism of Cayley graphs over an abelian group of order \(4p\) in polynomial time
• Circulant graphs: efficient recognizing and isomorphism testing
• On G-arc-regular dihedrants and regular dihedral maps
• scientific article; zbMATH DE number 3955189 (Why is no real title available?)
• scientific article; zbMATH DE number 4055624 (Why is no real title available?)
• scientific article; zbMATH DE number 57367 (Why is no real title available?)
• On the Cayley isomorphism problem for Cayley objects of nilpotent groups of some orders
• A family of permutation groups with exponentially many nonconjugated regular elementary abelian subgroups
• On decomposability of simple cyclic triple systems
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• scientific article; zbMATH DE number 4116532 (Why is no real title available?)
• Monomial isomorphisms of cyclic codes
• Two families of graphs that are Cayley on nonisomorphic groups
• Cayley graphs of more than one abelian group
• Generalized dihedral CI-groups
• On Cayley representations of finite graphs over abelian p-groups
• The number of cyclic configurations of type \((v_{3})\) and the isomorphism problem
• Isomorphisms of cyclic combinatorial objects
• Parker vectors for infinite groups
• Isomorphisms of cubic Cayley graphs on dihedral groups and sparse circulant matrices
• On dihedrants admitting arc-regular group actions
• Testing isomorphism of circulant objects in polynomial time
• Non-Cayley-isomorphic Cayley graphs from non-Cayley-isomorphic Cayley digraphs
• Sparsity of stable primes for dynamical sequences
• Some bounds on the number of cyclic Steiner 2-designs
• The isomorphism problem for Cayley ternary relational structures for some abelian groups of order \(8p\)
• Finding a cycle base of a permutation group in polynomial time
• On the BCI problem
• Further restrictions on the structure of finite DCI-groups: an addendum
• The isomorphism problem for abelian projective planes
• On isomorphisms of circulant digraphs of bounded degree

This page was built for publication: On the isomorphism problem for cyclic combinatorial objects

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