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.

Improve this question
$\endgroup$
10
  • 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
    Commented Oct 7, 2014 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
    Commented Oct 8, 2014 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
    Commented Oct 8, 2014 at 12:19
  • 1
    $\begingroup$ @verret: That looks like an answer and I encourage you to post it as such. $\endgroup$
    – Timothy Chow
    Commented Oct 8, 2014 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
    Commented Oct 9, 2014 at 4:29

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • 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
    Commented Oct 9, 2014 at 2:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .