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.

  • $\begingroup$ No, he is asking for a Gray code or Hamiltonian path from the identity to the desired sequence. Because of parity, some permutations will just miss out on a Hamiltonian path. Gerhard "Maximal Is What's Wanted, Right?" Paseman, 2016.04.06. $\endgroup$ – Gerhard Paseman Apr 6 '16 at 22:04
  • $\begingroup$ Actually, it depends on what the poster means by subsequence, and whether repetitions of transpositions are allowed. Gerhard "Subsequence Contiguity Is Important Here" Paseman, 2016.04.06. $\endgroup$ – Gerhard Paseman Apr 6 '16 at 22:09
  • $\begingroup$ I see. The term minimal is 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
  • $\begingroup$ @Gerry, Not really. If the idea is to find the smallest sequence of transpositions, then one can do it in under n-1 transpositions. However, the poster wants to know if there is a large minimal sequence. I can imagine a tour of S_n through various transpositions before applying (n,n+1). It is not clear to me if this tour is a minimal sequence however. Gerhard "Again, What Is A Subsequence?" Paseman, 2016.04.06. $\endgroup$ – Gerhard Paseman Apr 7 '16 at 0:06

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.

| cite | improve this answer | |
  • $\begingroup$ You can save checking some cases with the following observation: if t is a transposition, s is a permutaton which is a sequence of transpositions, and ts=st, then tst can't appear in a minimal sequence. Gerhard "There May Be Other Shortcuts" Paseman, 2016.04.06. $\endgroup$ – Gerhard Paseman Apr 7 '16 at 6:15
  • $\begingroup$ Why don't you apply the next transpositions to green permutations? As far as I understand, the subsequence does not need to consist of consecutive terms of the initial sequence. Also, $n\log n$ surely is not achievable, because you cannot reverse the order by using $(i,i+1)$ in less than $n\choose 2$ steps, due to the number of inversions changing by 1 at each step. $\endgroup$ – Ilya Bogdanov Apr 7 '16 at 7:19
  • $\begingroup$ The longest initial substring of $T$ that achieves $R$ can be arbitrarily large compared to to the minimal subsequence of $T$ that achieves $R$: consider the case that applying only the last transposition by itself is sufficient to obtain $R$, and the prefix just shuffles the permutation back and forth while arriving at the initial situation after transposition $T_{m-1}$. I am interested in the distinction between polynomial and superpolynomial for the length of minimal sequences for all $n$; not in getting bounds for individual small cases. $\endgroup$ – Bart Jansen Apr 7 '16 at 11:03
  • $\begingroup$ @Ilya, you are right about computing s'=st_i for green s: Not doing so misses out on coloring s' green earlier. It may be that the ending value of i is unchanged though. That would be a worthy problem to ask. Bart, indeed an arbitrary string for R can be arbitarily long, but you are asking for large minimal strings, which can't be arbitarily long as your post points out. Also, Ilya's inversion count changing by 1 does not always apply to give a quadratic in n lower bound. I think you will find i=9 for n=5. Gerhard "Go Check A Billion Cases" Paseman, 2016.04.07. $\endgroup$ – Gerhard Paseman Apr 7 '16 at 15:13

Your Answer

