Minimal Factorizations of Permutations into Star Transpositions

J. Irving; A. Rattan

doi:10.46298/dmtcs.3595

J. Irving ; A. Rattan - Minimal Factorizations of Permutations into Star Transpositions

dmtcs:3595 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3595

Minimal Factorizations of Permutations into Star TranspositionsConference paper

Authors: J. Irving ¹; A. Rattan ²

1 Department of Mathematics and Computing Science [Halifax]
2 Department of Mathematics [Cambridge]

[en]
We give a compact expression for the number of factorizations of any permutation into a minimal number of transpositions of the form $(1 i)$. Our result generalizes earlier work of Pak ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) in which substantial restrictions were placed on the permutation being factored.

[fr]
Nous présentons une expression compacte pour le nombre de factorisations minimales d'une permutation arbitraire de transposition de la forme $(1 i)$. Ce résultat généralise le travail passé de Pak ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) dans lequel des restrictions substantielles sont imposées sur la permutation étant factorisée.

https://doi.org/10.46298/dmtcs.3595

Source: HAL:hal-01185128v1

Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Section: Proceedings

Published on: January 1, 2008

Imported on: May 10, 2017

Keywords: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] factorizations, permutations, star transpositions, symmetric group

Funding:

Source : OpenAIRE Graph

Funder: Natural Sciences and Engineering Research Council of Canada

Bibliographic References

17 Documents citing this article

Jiayuan Wang, 2023, A note on fully commutative elements in complex reflection groups, Discrete Mathematics, 346, 12, pp. 113611, 10.1016/j.disc.2023.113611.

Ömer Eğeci̇oğlu;Elif Saygi;Zülfükar Saygi, 2023, Euler numbers and diametral paths in Fibonacci cubes, Lucas cubes and alternate Lucas cubes, Discrete Mathematics Algorithms and Applications, 16, 03, 10.1142/s1793830923500271.

Angèle M. Foley;Alejandro H. Morales;Amarpreet Rattan;Karen Yeats, 2022, Combinatorial and Algebraic Enumeration: a survey of the work of Ian P. Goulden and David M. Jackson, Algebraic Combinatorics, 5, 6, pp. 1205-1226, 10.5802/alco.269, https://doi.org/10.5802/alco.269.

Bridget Eileen Tenner, 2021, Star factorizations and noncrossing partitions, arXiv (Cornell University), 344, 7, pp. 112428, 10.1016/j.disc.2021.112428, http://arxiv.org/abs/2004.03286.

Claus Köstler;Alexandru Nica, 2020, A Central Limit Theorem for Star-Generators of $${S}_{\infty }$$, Which Relates to the Law of a GUE Matrix, Journal of Theoretical Probability, 34, 3, pp. 1248-1278, 10.1007/s10959-020-01029-6.

Valentin Féray;Igor Kortchemski, 2019, The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees, Annales Henri Lebesgue, 1, pp. 149-226, 10.5802/ahl.5, https://doi.org/10.5802/ahl.5.

Dohan Kim, 2016, Sorting on graphs by adjacent swaps using permutation groups, Computer Science Review, 22, pp. 89-105, 10.1016/j.cosrev.2016.09.003.

Eddie Cheng;Li Li;László Lipták;Sangho Shim;Daniel E. Steffy, 2016, On the Problem of Determining which (n, k)-Star Graphs are Cayley Graphs, Graphs and Combinatorics, 33, 1, pp. 85-102, 10.1007/s00373-016-1741-8.

Eddie Cheng;Ke Qiu;Zhizhang Shen, 2014, The number of shortest paths in the (n, k)-star graph, Discrete Mathematics Algorithms and Applications, 06, 04, pp. 1450051, 10.1142/s1793830914500517.

Dohan Kim, 2013, Task swapping networks in distributed systems, arXiv (Cornell University), 90, 11, pp. 2221-2243, 10.1080/00207160.2013.772985, http://arxiv.org/abs/1107.1851.

Eddie Cheng;Jerrold W. Grossman;Ke Qiu;Zhizhang Shen, 2013, The number of shortest paths in the arrangement graph, Information Sciences, 240, pp. 191-204, 10.1016/j.ins.2013.03.035.

Bridget Eileen Tenner, 2012, A combinatorial proof of symmetry among minimal star factorizations, Discrete Mathematics, 312, 16, pp. 2482-2490, 10.1016/j.disc.2012.04.021.

David M. Jackson;Craig A. Sloss, 2012, Character-theoretic techniques for near-central enumerative problems, Journal of Combinatorial Theory Series A, 119, 8, pp. 1665-1679, 10.1016/j.jcta.2012.05.004.

Emma Yu Jin;Christian M. Reidys, 2011, Random induced subgraphs of Cayley graphs induced by transpositions, Discrete Mathematics, 311, 21, pp. 2496-2511, 10.1016/j.disc.2011.07.027.

Valentin Féray, 2011, Partial Jucys–Murphy elements and star factorizations, arXiv (Cornell University), 33, 2, pp. 189-198, 10.1016/j.ejc.2011.09.035, http://arxiv.org/abs/0904.4854.

Eddie Cheng;Jerrold W. Grossman;László Lipták;Ke Qiu;Zhizhang Shen, 2010, Distance formula and shortest paths for the (n,k)-star graphs, Information Sciences, 180, 9, pp. 1671-1680, 10.1016/j.ins.2010.01.016.

Eddie Cheng;Ke Qiu;Zhi Zhang Shen, 2010, The Number of Shortest Paths in the (n, k)-Star Graphs, Lecture notes in computer science, pp. 222-236, 10.1007/978-3-642-17458-2_19.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 331 times.

This article's PDF has been downloaded 529 times.