×

The equivalence of two cyclic objects on \(pq\) elements. (English) Zbl 0859.05014

A cyclic object on \(n\) elements is a combinatorial structure on \(\{0,1,\dots,n-1\}\) which has an \(n\)-cycle in its automorphism group. Examples of classes of cyclic objects are circulant graphs or digraphs or cyclic block designs. For any such class the symmetric group on \(\{0,1,\dots,n-1\}\) induces an equivalence relation. Since most permutations, when applied to a cyclic object, will produce an object that is not cyclic, the equivalence classes are much smaller than in the general case without cyclicity assumption. Depending on the object class, and on the number-theoretic properties of \(n\), it has been shown in many cases that only equivalence by multipliers is possible. Pálfy showed that this is the case for any class of cyclic objects if \(\text{gcd}(n,\varphi(n))=1\). In this paper, the author shows that for \(n=pq\) with \(p\), \(q\) primes in the case \(\text{gcd}(n,\varphi(n))\neq1\) there are still only few possibilities: there is a list of at most \(\varphi(n)\) permutations such that equivalence of cyclic objects on \(n\) elements is possible only by these permutations. They have a piecewise structure of a multiplier.

MSC:

05A99 Enumerative combinatorics
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
05E20 Group actions on designs, etc. (MSC2000)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI

References:

[1] Alspach, B.; Parsons, T. D., Isomorphism of circulant graphs and digraphs, Discrete Math., 25, 97-108 (1979) · Zbl 0402.05038
[2] Babai, L., Isomorphism problem for a class of point-symmetric structures, Acta Mathematica Academiae Scientiarum Hungaricae, 29, 329-336 (1977) · Zbl 0378.05035
[3] Bays, S., 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-IV, Comment. Math. Helv., 3, 307-325 (1931) · JFM 57.1338.07
[4] Brand, N.; Huffman, W. C., Topological invariants of 2-designs arising from difference families, J. Combin. Theory Ser. A, 36, 253-278 (1984) · Zbl 0538.05009
[5] Colbourn, M. J.; Mathon, R. A., On cyclic Steiner 2-designs, Ann. Discrete Math., 7, 215-253 (1980) · Zbl 0438.05012
[6] W.C. Huffman, On the equivalence of cyclic codes of length \(p^m\); W.C. Huffman, On the equivalence of cyclic codes of length \(p^m\) · Zbl 0859.05014
[7] Huffman, W. C.; Job, V.; Pless, V., Multipliers and generalized multipliers of cyclic objects and cyclic codes, J. Combin. Theory Ser. A, 62, 183-215 (1993) · Zbl 0772.94011
[8] Lambossy, P., Sur une maniere de differencier les fonctions cycliques d’une forme donnee, Comment. Math. Helv., 3, 69-102 (1931) · JFM 57.1339.01
[9] Leon, J. S.; Masley, J. M.; Pless, V., Duadic codes, IEEE Trans. Inform. Theory IT-30, 709-714 (1984) · Zbl 0575.94013
[10] Mac Williams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland New York · Zbl 0369.94008
[11] Pálfy, P. P., Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. Theory, 8, 35-43 (1987) · Zbl 0614.05049
[12] Phelps, K. T., Isomorphism problems for cyclic block designs, Ann. Discrete Math., 34, 385-392 (1987) · Zbl 0647.05008
[13] Phelps, K. T., Isomorphism of circulant combinatorial structures, Ars Combin., 24, 195-210 (1987), A · Zbl 0721.05010
[14] Phelps, K. T.; Vanstone, S. A., Isomorphism of strong starters in cyclic groups, J. Combin. Theory Ser. A, 57, 287-293 (1991) · Zbl 0739.20006
[15] Pless, V., Introduction to the Theory of Error Correcting Codes (1989), Wiley: Wiley New York · Zbl 0698.94007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.