The Identity Transform of a Permutation and its Applications

• Autorzy: Frosini A. , Battaglino D. , Rinaldi S. , Socci S.

Identyfikatory

DOI

10.3233/FI-2015-1271

• Języki publikacji: EN

Abstrakty

EN

Starting from a Theorem by Hall, we define the identity transform of a permutation π as C(π) = (0 + π(0), 1 + π(1), ..., (n - 1) + π(n - 1)), and we define the set Cn = {(C(π) : π ∈ S_n}, where S_n is the set of permutations of the elements of the cyclic group Z_n. In the first part of this paper we study the set C_n: we show some closure properties of this set, and then provide some of its combinatorial and algebraic characterizations and connections with other combinatorial structures. In the second part of the paper, we use some of the combinatorial properties we have determined to provide a different algorithm for the proof of Hall's Theorem.

Słowa kluczowe

EN

transformations; permutations; cyclic groups; combinatorial analysis; set theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 2/3
• Strony: 191--205
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Frosini A.

• Dipartimento di Matematica e Informatica viale Morgagni 67, 50134, Firenze, Italy

autor

Battaglino D.

• Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche Pian dei Mantellini, 44, 53100, Siena, Italy

autor

Rinaldi S.

• Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche Pian dei Mantellini, 44, 53100, Siena, Italy

autor

Socci S.

• Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche Pian dei Mantellini, 44, 53100, Siena, Italy

Bibliografia

• [1] M. Bona, Combinatorics of permutations, Chapman-Hall and CRC Press (2004).
• [2] A. Del Lungo, Reconstructing permutation matrices from diagonal sums, Theor. Comput. Sci. 281 (2002) 235–249.
• [3] A. Del Lungo, C. Marini, E. Mori, A polynomial time algorithm for finding zero-sums, Disc. Math. 309(9) (2009) 2658-2662.
• [4] P. Erdös, A. Ginzburg, A. Ziv, A theorem in additive number theory, Bull. Res. Council, Israel F, 10 (1961) 41-43.
• [5] M. Hall, Jr., A combinatorial problem on abelian groups, Proc. Amer. Math. Soc. 3 (1952) 584–587.
• [6] M. Hall, Jr., A survey of difference sets, Proc. Amer. Math. Soc. 7 (1956) 975–986.
• [7] F. Salzborn, G. Szekeres, A problem in combinatorial group theory, Ars Combinatoria 7 (1979) 3–5.