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 TranspositionsArticle
Authors: J. Irving 1; A. Rattan 2
NULL##NULL
J. Irving;A. Rattan
1 Department of Mathematics and Computing Science [Halifax]
2 Department of Mathematics [Cambridge]
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.
Ömer Eğeci̇oğlu;Eli̇f Saygi;Zülfükar Saygi, 2023, Euler numbers and diametral paths in Fibonacci cubes, Lucas cubes and alternate Lucas cubes, arXiv (Cornell University), 10.1142/s1793830923500271, https://arxiv.org/abs/2210.13849.
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.
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, arXiv (Cornell University), 34, 3, pp. 1248-1278, 10.1007/s10959-020-01029-6, https://arxiv.org/abs/1807.05633.
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.
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.
Emma Yu Jin;Christian M. Reidys, 2011, Random induced subgraphs of Cayley graphs induced by transpositions, arXiv (Cornell University), 311, 21, pp. 2496-2511, 10.1016/j.disc.2011.07.027.
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, Lecture notes in computer science, The Number of Shortest Paths in the (n, k)-Star Graphs, pp. 222-236, 2010, 10.1007/978-3-642-17458-2_19.