5
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Apr 6, 2016 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$ Apr 6, 2016 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$ Apr 7, 2016 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$ Apr 7, 2016 at 0:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Apr 7, 2016 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$ Apr 7, 2016 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$ Apr 7, 2016 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$ Apr 7, 2016 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.