Creating an 𝑛 = 4 Pancake Graph in 3D

CREATING AN n= 4 PANCAKE GRAPH IN 3D RIKO URYU, YUKI TAKAMOTO, AND MAYUMI YASUDA Abstract. Graph theory has a problem called the “Pancake Problem”, which asks how many flip operations are required to sort pancakes of different sizes in order from the smallest to the largest by using only a spatula. It is concerned with sorting a permutation (a stack of pancakes of different sizes) using only prefix reversals (operations of pancake flipping). In this research, to study the relationships between permutations that result from flip operations, a pancake graph is constructed for n= 4. When the graph is created in 3D, a highly symmetric three-layer structure is obtained. In addition, we succeed in applying the structure to a new form by putting four hexagons in the positions of each face of a regular tetrahedron. 1. Introduction In 1975, Jacob E. Goodman (under the pseudonym Harry Dweighter [1]) first posed the following problem: The chef in our place is sloppy, and when he prepares a stack of pancakes, they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (in terms of n) that I will ever have to use to rearrange them? The “Pancake Problem” asks how many prefix reversals are sufficient to sort any permutation to the identity [3]. A pancake flipping refers to the operation where, in a stack of n(the number of pancakes) pancakes of different sizes, a number of pancakes from the top are flipped simultaneously. In pancake flipping, when “flipj” indicates the operation of flipping jpancakes from the top, flip2,flip3, and flip4correspond to the transpositions (1 2), (1 3), and (1 4)(2 3), respectively. The flip operation to arrange pancakes (which can be represented by a permutation rearrangement by flipping) can be illustrated in the pancake graph, which is a Cayley graph of the symmetric group Sn. The value of the maximum distance between two vertices, which is called the diameter of the pancake graph, is evaluated by inequality (e.g. [2]). But the exact value for an arbitrary large nis unknown (see [4]). On the other hand, in the case where n= 4, we are able to examine the relationship of permutations by using the Hasse diagram of S4based on the Bruhat order and the bubble-sort graph, which is the Cayley graph of S4with respect to the generating set {(1 2),(2 3),(3 4)}. When the Hasse diagram is grasped in 3D, the form is called a truncated octahedron, which covers the lack of symmetry of the 1 2 RIKO URYU, YUKI TAKAMOTO, AND MAYUMI YASUDA Hasse diagram. Following the structures of the Hasse diagram and the truncated octahedron, in this research, we consider whether it is possible to represent the performance of flipping on permutations in a 3D graphic form so that it becomes easy to grasp visually. [4 3 2 1] [4 2 3 1] [4 3 1 2][3 4 2 1] [4 1 3 2][3 4 1 2][4 2 1 3][2 4 3 1][3 2 4 1] [4 1 2 3][1 4 3 2][3 1 4 2][2 3 4 1][3 2 1 4] [2 4 1 3] [1 2 4 3][2 1 3 4] [1 3 2 4] [1 4 2 3][1 3 4 2][3 1 2 4][2 3 1 4] [2 1 4 3] [1 2 3 4] Hasse Diagram Truncated octahedron based on the Hasse diagram[5] [2 1 4 3] [4 2 1 3] [2 4 1 3] [2 4 1 3] [2 1 4 3] [4 2 1 3] [2 4 1 3] [4 2 1 3] [2 4 1 3] [2 1 4 3] [4 3 1 2] [3 4 1 2] [4 3 2 1] [3 4 2 1] [4 1 3 2] [4 2 3 1] [4 1 2 3] [3 1 4 2] [2 4 3 1] [3 2 4 1] [1 4 3 2] [1 4 2 3] [1 3 4 2] [3 1 2 4] [3 2 1 4] [2 3 4 1] [2 3 1 4] [2 1 3 4] [1 2 4 3] [1 2 3 4] [1 3 2 4] Figure 1. The Hasse diagram and the truncated octahedron. A comparison between the Hasse diagram of the symmetric group S4based on the Bruhat order (left) and its realization as a truncated octahedron in 3D space (right). 2. Main Result It is known that the pancake graph of degree nconsists of nsets of the pancake graph of degree n−1. In this research, we grasp an n= 4 pancake graph in 3D in order to contribute to better understanding of the performance of flipping in permutations. The following theorem is our main result (see Figure 9): Theorem 1. There exists a continuous map f:P4→R3such that its restriction f|V4to V4is injective, and for any σ∈S4, the sets f(V4),f(E4,2),f(E4,3), and f(E4,4)are invariant under ρ(σ). In the theorem above, P4is the pancake graph for n= 4, and V4is its vertex set. E4,2,E4,3, and E4,4are the edge set of P4corresponding to the flip oparations flip2,flip3and flip4, respectively. ρ:S4→GL3(R) is a well-known representation of S4. 3. Preliminaries 3.1. Permutations. Apermutation is a rearrangement of the numbers 1, 2, . . . , and n. We denote a permutation πrearranging 1, 2, . . . , and ninto π(1), π(2), . . . , and π(n) as π= [π(1) π(2) ··· π(n)] ∈Sn. Atransposition is an exchange of two numbers in a permutation. Notice that performing a transposition on a permutation from right makes the two numbers exchange their positions as the transposition indicates. CREATING AN n= 4 PANCAKE GRAPH IN 3D 3 For instance, transposition (1 2) performed on the permutation [3 4 1 2] is written as [3 4 1 2] ◦(1 2) = [4 3 1 2] (In this operation, the permutation [3 4 1 2] becomes the permutation [4 3 1 2].) An adjacent transposition is a transposition that exchanges natural numbers whose difference is one. 3.2. Pancake Graph. Let flipj∈Sn(j∈ {2,3, . . . , n}) be the permutation flipj(i) = (j−i+ 1 (if i≤j), i(if i > j). Then the set {flipj|j∈ {2,3, . . . , n}} is a generating set of Sn. The Cayley graph of Snwith respect to the generating set {flipj|j∈ {2,3, . . . , n}} is called the pancake graph Pnof degree n. Specifically, the vertex set Vnof Pn= (Vn, En) is Vn=Sn, and the edge set Enis given by En={{π, π ◦flipj}|π∈Sn, j ∈ {2,3, . . . , n}} . Remark 1.(1) For each j∈ {2,3, . . . , n}, define En,j := {{π, π ◦flipj}|π∈Sn}. If π′=π◦flipj, then π=π′◦flipjalso holds. Thus we have |En,j|=n! 2. Each edge in En,j corresponds to the operation flipjdefined in the next section. (2) Hereafter, we identify the vertex set Vnwith Sn. By regarding each edge {π, π′}as a path of length 1 connecting the two points πand π′, the pancake graph Pncan be viewed as a metric space. Example 1. The n= 2 pancake graph. (If n= 2, the flip operation performed is only flip2.) [2 1][1 2] Figure 2. The pancake graph P2.Geometric representation of the graph for degree n= 2, where the only valid prefix reversal is the flip2operation. Example 2. The n= 3 pancake graph. (If n= 3, the flip operation performed is flip2and flip3.) In Figure 3, the edges in E3,2(i.e. the edges corresponding to flip2) are represented by blue lines, and the edges (i.e. the edges corresponding to flip2) in E3,3 by green lines. 4. n= 4 Pancake Flipping Consider an arrangement of npancakes of different sizes, and flip the pancakes from the top. 4 RIKO URYU, YUKI TAKAMOTO, AND MAYUMI YASUDA [1 2 3] [2 1 3] [1 3 2] [3 1 2] [2 3 1] [3 2 1] Figure 3. The pancake graph P3.Visualization of the n= 3 graph where blue edges denote flip2transpositions and green edges denote flip3prefix reversals. 4.1. n= 4 Case. Consider the flipping in the situation of n= 4. We number the pancakes 1, 2, 3, and 4 from the smallest to the largest to represent the arrangement of the pancakes. For instance, the arrangement of pancakes in Figure 4a is represented as the permutation [1 2 3 4]. We define the operation of flipping j pancakes from the top as flipj. 4.2. Flip2.The definition of flip2is “the operation of flipping 2 pancakes from the top”, which means the first and second pancakes exchange their positions. This corresponds to the transposition (1 2), and the stack of pancakes in Figure 4b shows the result of performing flip2on the stack of pancakes in Figure 4a. flip2:= (1 2) 4.3. Flip3.The definition of flip3is “the operation of flipping 3 pancakes from the top”, which means the first and third pancakes are exchanged, leaving the second pancake to stay. This corresponds to the transposition (1 3), and the stack of pancakes in Figure 4c shows the result of performing flip3on the stack of pancakes in Figure 4a. flip3:= (1 3) 4.4. Flip4.The definition of flip4is “the operation of flipping 4 pancakes from the top”, which means all 4 pancakes are turned upside down so that the first and fourth pancakes exchange and the second and third pancakes exchange their positions. This corresponds to the permutation, and the stack of pancakes in Figure 4d shows the result of performing flip4on the stack of pancakes in Figure 4a. flip4:= (1 4)(2 3) 4 2 3 1 (a) Identity [1234] 3 2 1 4 (b) flip2result 3 2 1 4 (c) flip3result 3 2 1 4 (d) flip4result Figure 4. Standard prefix reversal operations on n= 4 pancakes. Figures (a) through (d) illustrate the identity configuration and the results of the three generating flips. CREATING AN n= 4 PANCAKE GRAPH IN 3D 5 Upon the set of the permutation of degree n, the graph that is made by connecting permutations that transition into each other through pancake flipping is called a pancake graph. This graph connects permutations, indicating permutations as vertices and flippings as edges. 5. An n= 4 Pancake Graph 5.1. Our first attempt: Since there are 4! = 24 permutations of degree four, the pancake graph for n= 4 has 24 vertices. We attempt to create a symmetric 2D pancake graph for n= 4 by connecting permutations starting from the permutation [1 2 3 4], the base. However, when drawing the graph with the rule in which permutations connected by the same number of edges from the permutation [1 2 3 4], the base, are placed in the same layer, we find that some permutations in the same layer are adjacent to each other, resulting in a complicated diagram. Therefore, in this study, we shall consider the pancake graph in 3D. 5.2. The use of Euler’s polyhedron formula: In the process of creating a threedimensional pancake graph, we use Euler’s polyhedron formula to predict the shape of the pancake graph. Euler’s polyhedron formula: If the polyhedron has vvertices, eedges, and f faces, then v−e+f= 2 In a pancake graph, permutations correspond to vertices, so for the permutations of degree four, there are 24 permutations, so v= 24. Three types of flip, there are 36 of them in total, so e= 36. Therefore, we get 14 for fand predict that the shape is a tetradecahedron. In the figures below, the edges for flip2= (1 2) are represented by blue lines, the edges for flip3= (1 3) by green lines, and the edges for flip4= (1 4)(2 3) by red lines. We first consider the faces formed by each pair of flips (edges). Case 1. For the face formed by flip2= (1 2), and flip3= (1 3), starting from the base permutation [1 2 3 4], we obtain [1 2 3 4] ◦(1 2) ◦(1 3) = [3 1 2 4], which gives the mapping 1 7→ 3, 2 7→ 1, 3 7→ 2, and 4 7→ 4. To return to the original permutation [1 2 3 4], The numbers return to their initial position by three steps (1 7→ 37→ 27→ 1), so three sets of green and blue edges are needed. Forming a hexagon as shown in Figure 5a, four such hexagons are created in total. Case 2. For the face formed by flip2= (1 2), and flip4= (1 4)(2 3), starting from [1 2 3 4], we obtain [1 2 3 4] ◦(1 2) ◦(1 4)(2 3) = [4 3 1 2], which gives the mapping 17→ 4, 2 7→ 3, 3 7→ 1, and 4 7→ 2. The numbers return to their initial positions by four steps (1 7→ 47→ 27→ 37→ 1), so four sets of green and red edges are needed. Forming an octagon as shown in Figure 5b, three such octagons are created in total. Case 3. For the face formed by flip3= (1 3), and flip4= (1 4)(2 3), starting from [1 2 3 4], we obtain [1 2 3 4] ◦(1 3) ◦(1 4)(2 3) = [4 1 2 3], which gives the mapping 17→ 4, 2 7→ 1, 3 7→ 2, and 4 7→ 3. The numbers return to their initial positions by four steps (1 7→ 47→ 37→ 27→ 1), so four sets of green and red edges are needed. Forming an octagon as shown in Figure 5c, three such octagons are created in total. (Results) Since there are 24 permutations of degree four in total, and three edges can be drawn 6 RIKO URYU, YUKI TAKAMOTO, AND MAYUMI YASUDA [abcd] [bacd] [cabd] [acbd][bcad] [cbad] (a) flip2and flip3 [abcd] [bacd] [dcab] [cdab] [badc][abdc] [cdba] [dcba] (b) flip2and flip4 [abcd] [cbad] [dabc] [badc] [cdab][adcb] [bcda] [dcba] (c) flip3and flip4 Figure 5. Canonical cycles in the P4pancake graph. (a) The hexagonal cycle formed by alternating flip2and flip3. (b, c) The two distinct types of octagonal cycles formed by alternating flip2/flip4and flip3/flip4operations, respectively. from a permutation, we need four hexagons with blue edges and green edges, three octagons with green edges and red edges, and three octagons with blue and red edges. In other words, an n= 4 pancake graph consists of ten polygons, which contradicts our prediction based on Euler’s polyhedron formula that an n= 4 pancake graph is a tetradecahedron in 3D. Therefore, it is impossible to form a polyhedron by combining these polygons. Figure 6. Assembled wireframe model of the n= 4 pancake graph. This physical realization demonstrates the threelayer structure and the highly symmetric connectivity resulting from the three types of flip operations. By using wire for the edges, we are able to create a three-layer structure as shown in Figure 6. Regarding the structure of Figure 6, each layer is depicted in Figure 7. This structure has four hexagons, formed by flip2and flip3(from Figure 5a), arranged on the sides, connected to an octagon on the top layer (formed by flip3 CREATING AN n= 4 PANCAKE GRAPH IN 3D 7 and flip4, from Figure 5c) and an octagon on the bottom layer (formed by flip2 and flip4, from Figure 5b). (a) Top layer (b) Middle layer (c) Bottom layer Figure 7. Layer-wise decomposition of the P43D structure. The model is partitioned into three distinct layers to illustrate the rotational symmetry of the hexagonal and octagonal faces. Focusing on the fact that our structure contains four hexagons, we consider whether it is possible to place those hexagons on the positions of each face of a regular tetrahedron. The hexagons, which we place as the bases, consist of flip2 and flip3. This means that transpositions are performed on numbers except the fourth one, and the fourth number of all six permutations in the same hexagon is consistent. Also, we can find that for the red edges, which represent flip4, two pieces are drawn from each hexagon. So, in applying the structure to a new form, we need to focus on these and connect the edges. We attempt to create a highly symmetrical structure by positioning the four hexagons from Figure 5a on the faces of a regular tetrahedron. By connecting the edges based on the rule that the shape does not change its shape, no matter how it is rotated (shown in Figure 7), the new form is obtained (Figure 9). 5.3. Highly Symmetrical Form. Let σ1, σ2, σ3∈S4be defined as σ1:= (1 2), σ2:= (3 4), and σ3:= (2 3 4). These form a generating set of S4. The symmetric group S4acts isometrically on R3from the left via the representation ρ:S4→ GL3(R) defined by ρ(σ1) =    1 30−2√2 3 010 −2√2 30−1 3   , ρ(σ2) =   100 0−1 0 001 , ρ(σ3) =    −1 2 √3 20 −√3 2−1 20 0 0 1  . Remark 2.Let v1, v2, v3, v4∈R3be v1:=   0 0 1 , v2:=   −2√2 3 0 −1 3  , v3:=    √2 3 √6 3 −1 3   , v4:=    √2 3 −√6 3 −1 3   . Then, these are the vertices of a regular tetrahedron centered at the origin, and for any σ∈S4,ρ(σ)(vi)=vσ(i)holds for i= 1,2,3,4. 8 RIKO URYU, YUKI TAKAMOTO, AND MAYUMI YASUDA Theorem 1. There exists a continuous map f:P4→R3such that its restriction f|V4to V4is injective, and for any σ∈S4, the sets f(V4),f(E4,2),f(E4,3), and f(E4,4)are invariant under ρ(σ). Proof. For π= [π(1) π(2) π(3) π(4)] ∈V4, define f(π) = 1 3vπ(1) +1 6vπ(2) +1 2vπ(3). Then, for any πsuch that π(4) = d, the point f(π) lies on the triangle formed by the vertices va, vb, vc, and such 6 points form a hexagon, where {a, b, c, d}={1,2,3,4} (Figure 8). Consequently, the restriction f|V4is injective. va vbvc [b c a d] [c b a d] [a b c d] [b a c d][c a b d] [a c b d] Figure 8. f(P4) in the triangle formed by the vertices va, vb, vc Furthermore, by Remark 2, for any σ∈S4, we have: ρ(σ)f(π)=ρ(σ) (f([π(1) π(2) π(3) π(4)])) = f([σ(π(1)) σ(π(2)) σ(π(3)) σ(π(4))]) = f(σ◦π), which implies that f(V4) is invariant under ρ(σ). Regarding the edges, each {π, π ◦ flipj} ∈ E4,j can be mapped continuously to the line segment connecting f(π) and f(π◦flipj). Then, similarly, since ρ(σ)f(π) = f(σ◦π) and ρ(σ)f(π◦flipj) = f(σ◦(π◦flipj))=f((σ◦π)◦flipj), it follows that f(E4,j) is also invariant under ρ(σ). □ CREATING AN n= 4 PANCAKE GRAPH IN 3D 9 Figure 9. f(P4) Figure 9demonstrates how f(P4) lies in R3. This figure is available on https://www.geogebra.org/calculator/sjfnx9n6, where the figure can be rotated and viewed from any angle. A movie in which the figure rotates around an axis is also available on https://drive.google.com/file/d/1PuAIyi7m9yiGT8TxJIZKfdPdyuVTDZtY/view. 6. Prospects In this research, we obtain a three-layer structure with high symmetry when the graph is created in three dimensions. In addition to the fact that the performances of adjacent transpositions can be grasped using a truncated octahedron, we succeed in showing the performance of flipping in a simple 3D graphic form. However, we cannot grasp the relationship of permutations by the performance of flipping at a glance with this structure. As our prospect, we will analyze the new form of the structure that we have introduced, and will approach the examination of the diameter of the pancake graph. References [1] H. Dweighter, “Elementary Problem E2569,” The American Mathematical Monthly 82(10) (1975), 1009–1010. [2] W. H. Gates and C. H. Papadimitriou, “Bounds for sorting by prefix reversal,” Discrete Mathematics 27(1) (1979), 47–57. [3] Z. Hunter, “A new upper bound to (a variant of) the pancake problem,” arXiv preprint arXiv:2211.14678 (2022). https://arxiv.org/abs/2211.14678