Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a transposition $t_i$ to (a permutation of) $S$, it exchanges the elements at positions $a_i$ and $b_i$ in the sequence.

Applying all transpositions $t_1, \ldots, t_m$ one by one on $S$ yields a final permutation $R$. Call a transposition sequence $T$ *minimal* if there is no proper subsequence $T'$ of $T$ whose application to $S$ would result in the same permutation $R$. My question is the following: what is the maximum length of a minimal transposition sequence, in terms of $n$? It is clear that this maximum is at most $n!$: if we have a sequence with more than $n!$ transpositions, then when applying the transpositions in $T$ there will be 2 points at which we have obtained the same intermediate permutation, and the transpositions in between can be removed from the sequence without changing the final outcome. What I am wondering is the following: can there be a polynomial upper bound on the length of a minimal transposition sequence? If not, then what does a minimal transposition sequence of superpolynomial length look like?

Edit: Apologies for my elementary exposition of the question; I'm a computer scientist and relatively unfamiliar with the literature in group theory. Let me clarify some points: my use of subsequence follows that of Wikipedia. The sequence of transpositions $T$ will, in general, contain repeated transpositions, otherwise a polynomial ($n^2$) bound on the length of any such sequence would be trivial. I do not think my question can be rephrased in terms of properties of the Cayley graph with a given set of transpositions as generators of the symmetric group, because I care for the *order* in which the transpositions are applied: in making a given sequence $T$ minimal you are allowed to remove transpositions from the sequence, but not to re-order them.

minimalis a bit misleading. As @GerhardPaseman says, this is looking for the longest non-self-intersecting walk on the Cayley graph of $S_n$. $\endgroup$ – Anthony Quas Apr 7 '16 at 0:05