Lesson plan

Pancake graph

In the mathematical field of graph theory, the pancake graph P n or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. Obtaining the pancake number is equivalent to the problem of obtaining the diameter of the pancake graph. The pancake graph of dimension n, P n , is a regular graph with n! vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has \dfrac{1}{2} ~ n! \left(n-1\right) edges. P n can be constructed recursively from n copies of P n−1 , by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Back to article

Article summary

In the mathematical field of graph theory, the pancake graph P n or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. Obtaining the pancake number is equivalent to the problem of obtaining the diameter of the pancake graph. The pancake graph of dimension n, P n , is a regular graph with n! vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has \dfrac{1}{2} ~ n! \left(n-1\right) edges. P n can be constructed recursively from n copies of P n−1 , by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.