Transpositional sequences and multigraphs

Abstract

When $\mathbf{t}:=⟨t_1,t_2,\dots ,t_k⟩$ is a sequence of transpositions on the finite set $n:=\{0,1,\dots ,n-1\}$, then $◯\mathbf{t}:=t_1\circ t_2\circ \cdots \circ t_k$ denotes the compositional product of the sequence. Our paper treats the set $\mathrm{Prod}(\mathbf{t})$ of all $◯\mathbf{s}$, where $\mathbf{s}$ is a sequence obtained by rearranging the terms of $\mathbf{t}$. The paper characterizes the set of all transpositional sequences $\mathbf{t}$ for which $\mathrm{Prod}(\mathbf{t})$ is the subset of a single congugacy class in the symmetric group $\mathrm{Sym}(n)$; we call such $\mathbf{t}$ {\it conjugacy invariant}. At the opposite extreme, the paper studies conditions under which $\mathbf{t}$ is {\it permutationally complete}, which is to say, those $\mathbf{t}$ for which either $\mathrm{Prod}(\mathbf{t})=\mathrm{Alt}(n)$ or $\mathrm{Prod}(\mathbf{t})=\mathrm{Sym}(n)\setminus \mathrm{Alt}(n)$.

20 pages, 20B30, 20B99