Department of Mathematics Calendar
Saúl Blanco Rodríguez, Indiana University, Cycles in the pancake and burnt pancake graph
- This event has passed.
The pancake graph has the elements of the symmetric group as vertices and there is an edge between two permutations if there is a prefix reversal that transforms one permutation into the other. One can similarly define the burnt pancake graph using signed permutations instead of permutations. Since these graphs are Cayley graphs, they have several interesting properties such as being regular and vertex transitive. Furthermore, one can prove that the pancake graph is weakly pancyclic and Hamiltonian (so one can embed cycles of length from its girth to a the number of vertices of the graph). We prove that the burnt pancake graph is also weakly pancyclic and Hamiltonian. Furthermore, the cycle structure of these graphs has connections with the classic pancake problem of sorting a stack of pancakes of different diameters using a chef spatula. For example, one can use the cycle structure to prove that there are polynomial expressions to count the number of pancake stacks that require k flips to be sorted for certain values of k. Analogous results are proven for burnt pancake stacks, also for certain values of k. In this talk, we will present these results and mention connections to computer science.