Pancake graph have least diameter & degree (log n/ log log n)

pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}.

pancake Graph with order-3 will be one single line with one hexagonal, labeled with permutation of node {123, 132, 213, 231, 312, 321}.

Similarly for order-4 graph will be with 4-hexagonal. enter image description here

This graph is in three dimension or four dimension? if this graph is in four dimension, then how graph will look like in three dimension?

  • 1
    $\begingroup$ What did you try? What do you think? To me, it seems clear that the dimension is at least 3. $\endgroup$ – Juho Jan 8 '14 at 12:37

Based on the example I infer the following structure.

The pancake graph seems to be defined with flipping pancakes in mind. For order $n$ we take all $n!$ permutations of the numbers $1,\dots,n$ as vertices of the graph. The vertices represent orderings of the pancakes, with the topmost pancake listed first, and the other pancakes are listed from top to bottom. The edges represent flips. Take any first $k>1$ numbers in a vertex, and reverse that prefix. An edges is added between those to vertices. Thus $i_1, \dots, i_k, i_{k+1}, \dots, i_n$ flips to $\overleftarrow{i_k, \dots, i_1}, i_{k+1}, \dots, i_n$.

With $n=3$ there are obviously $3! =6$ vertices. $123, 132, 213, 231, 312, 321$. Each node has degree 2 (i.e., has two neighbours) as I can flip topmost 2 pancakes or all 3 of them. From $123$ I thus have edges to $213$ and $321$. The other edges follow the same rule.

Your example figure has missing edges. All vertices should have three neighbours for $n=4$. So $1324$ should also be connected to $4231$ flipping all the pancakes.

The above diagram have dimension 4.

PS. The pancake graph is important in the context of "sorting by reversal", for instance giving bounds on the number of steps to sort any permutation into the identity permutation. This bound is of course the diameter of the pancake graph. The field has a famous paper by Papadimitrou and Gates (of Microsoft fame).

| cite | improve this answer | |
  • $\begingroup$ Thanks, Hendrik Jan, is here any fix pattern for assigning labels on nodes? means in which sequence node label will be assign? $\endgroup$ – Manish Kumar Jan 9 '14 at 5:12
  • 1
    $\begingroup$ The nodes and their labels are just all $n!$ permutations of $1,2,\dots,n$ for some $n$. So 6 for $n=3$ and 24 for $n=4$ as in the illustration. The edges are the 'flipping' relations. $\endgroup$ – Hendrik Jan Jan 9 '14 at 10:17

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