[Solved]: What is the order of the Pancake graph in Given example & what are the properties of Pancake graph?

Problem Detail: 

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.

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?

Asked By : Manish Kumar

Answered By : Hendrik Jan

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19578