Generating the symmetric group by three prefix reversals

2025/11/21 by Saúl A. Blanco, Blanco, Saúl A., M. P. Golubyatnikov +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05C25 #05E15 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Group Theory (math.GR)

paper · pdf · doi:10.48550/arxiv.2511.16959

openalex publication_date 2025/11/21 · openalex created_date 2025/11/25 · openalex updated_date 2026/07/28

Abstract

The cubic pancake graphs are Cayley graphs over the symmetric group Sym_n generated by three prefix reversals. There is the following open problem: characterize all the sets of three prefix reversals that generate Sym_n. We present a partial answer to this problem, in particular, we characterize all generating sets of three elements that contain at least one of the prefix reversals r₂, r₃, r_n-2, and r_n-1. We also give some computational results relating to the diameter and the girth of some cubic pancake graphs.

Citations

• CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)
• Lengths of Cycles in Generalized Pancake Graphs

Related

• Lengths of Cycles in Generalized Pancake Graphs
• Cycles in the burnt pancake graphs
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Presentations of Coxeter groups of type A, B, and D using prefix-reversal generators
• Cayley graph on symmetric groups with generating block transposition sets