5
$\begingroup$

Problem. Let $n\geq 2$ and let $T$ be the set of all permutations in $S_n$ of the form $$t_k:=\prod_{1\leq i\leq k/2}(i,k-i) \qquad \hbox{for $k=3,4,\ldots,n+1$}.$$ Find the least integer $f_n$ such that every $x \in S_n$ can be written as a product of at most $f_n$ elements from $T$.

This is part (ii) of Exercise 1.2.16 in Chapter 1 of Permutation Groups by Dixon and Mortimer (Springer 1996) and is labeled as an unsolved problem. It has been 18 years since the book was published (I guess there hasn't been any further edition yet), so I was wondering whether it is solved or not; if it is can somebody give me a hint? It looks very tough. I have solved part (i) of the exercise, showing that $T$ generates $S_n$, and showing that $2n-3$ is always an upper bound.

I asked it on math.stackexchange but did not get any answers there. I am an active member there, but here it is my first question; I hope it meets the standards here.

$\endgroup$
  • 3
    $\begingroup$ @Bhaskar Vashishth: (1) You asked this just 7 hours ago at math.stackexchange.com/questions/962121/…, so maybe you are a little impatient. (2) The book you mention is by Dixon and Mortimer. (3) The assertion you showed is exercise 1.2.16(i) there, your question is about the unsolved part (ii). $\endgroup$ – Peter Mueller Oct 7 '14 at 18:58
  • 2
    $\begingroup$ Isn't this just prefix reversal? In other words, you are asking for the diameter of the "pancake graph". This is open but see oeis.org/A058986 for lots of information. $\endgroup$ – verret Oct 8 '14 at 1:31
  • 3
    $\begingroup$ The standard name for this problem is "Pancake Sorting" and the Wikipedia article is pretty good en.wikipedia.org/wiki/Pancake_sorting . One fun fact is that this is the subject of Bill Gates only published paper in math cs.berkeley.edu/~christos/papers/… $\endgroup$ – David E Speyer Oct 8 '14 at 12:19
  • 1
    $\begingroup$ @verret: That looks like an answer and I encourage you to post it as such. $\endgroup$ – Timothy Chow Oct 8 '14 at 14:57
  • 1
    $\begingroup$ Another fun fact is that the problem was originally raised by an author writing under the pseudonym of Harry Dweighter ("harried waiter"). mathoverflow.net/questions/45185/… $\endgroup$ – Gerry Myerson Oct 9 '14 at 4:29
3
$\begingroup$

This problem is known as ''pancake sorting'' or ''sorting by prefix reversal''. Imagine you have a stack of pancakes numbered $1,2,3,\ldots$ starting from the top. Then $t_k$ corresponds to taking the top $k-1$ pancakes and ``flipping them'' (as a stack). The minimum number of flips needed to reach any given arrangement (alternatively, the diameter of the corresponding Cayley graph) is a well-known problem. The exact number is not known, but some decent bounds are.

More information can be found at :

http://en.wikipedia.org/wiki/Pancake_sorting

https://oeis.org/A058986

$\endgroup$
  • 2
    $\begingroup$ By the way, I knew about this problem previously but did not recognise it immediately. I computed a few of the values of the diameter in magma and then searched the OEIS for the corresponding sequence together with the word "diameter". The only hit was the right one. This is a good methodology to follow for this type of question. $\endgroup$ – verret Oct 9 '14 at 2:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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