Maximum size of minimal sequence of transpositions whose product is a given permutation 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.
 A: Thank you for clarifying the question.  (I would edit further to indicate subsequence is different from substring or subword, so not necessarily a contiguous portion of the given sequence.)  The short answer is I don't know, but I suspect the length is not superquadratic for reasons that will appear.
Pick a sequence T of transpositions on the n letters, set S to the singleton set of the identity permutation and i to 1. Now compute for each  uncolored (non-green) permutation s in S the permutation s' = st_i.  If s' is already in S, mark it green, otherwise add uncolored s' to S.  Then increment i. Check if all members of S are green.  If so stop, else loop back to 'Now'.Edit 2016.04.07: Thanks to Ilya Bogdanov, I should also compute s'=st_i for green s as well, and then color those s' instantly as I put them in S; I might get a smaller maximal value of i.  To address the concerns of the poster, this algorithm should be run for enough sequences T to determine the largest value of i given n.  Also, Ilya's suggestion of looking at inversion count using sequences of adjacent transpositions has merit, as it might lead to a quadratic in n lower bound on maximal i.  However, more rigor is needed to ensure minimality of a long enough sequence of adjacent transpositions.  End Edit 2016.04.07.
This will give you an algorithm to determine the longest initial substring of T which is minimal.  Once the algorithm stops, i is too big.  As S has the potential to be 2^i in size, and we stop after duplicating at most n! permutations in S, my gut says i is bounded by cnlog n and definitely by n^2.  However, this is not a proof, as there may be some holdouts.  Note though that if the initial segment duplicates a subset of permutations, then any sequence including that initial segment as a substring is not minimal.
For small values of n, it should be only mildly onerous to compute the maximal length of such a minimal sequence.  I predict that 4n^2 is a weak upper bound on i for all n.  If you choose substring instead of subsequence, I think the growth might be superpolynomial, and you can write a similar algorithm above to test it.
Gerhard "Needs Practice In Formatting Pseudocode" Paseman, 2016.04.06.
