TAOCP 5.1.1 Exercise 10
The truncated octahedron in Figure 1 is the permutohedron of order 4.
Exercise 10. [HM20] Consider Fig. 1 as a polyhedron in three dimensions. What is the diameter of the truncated octahedron (the distance between vertex 1234 and vertex 4321), if all of its edges have unit length?
Verified: yes
Solve time: 11m52s
Solution
The truncated octahedron in Figure 1 is the permutohedron of order 4. Its vertices are the 24 permutations of ((1,2,3,4)) embedded in the hyperplane (x_1+x_2+x_3+x_4=10) in (\mathbb{R}^4). Two vertices are connected by an edge exactly when the corresponding permutations differ by an adjacent transposition.
In the natural embedding (vertices = permutations of ((1,2,3,4))), the edge length is the distance between permutations that differ by an adjacent transposition. For example, (1234 = (1,2,3,4)) and (1243 = (1,2,4,3)) differ by ((0,0,-1,1)), giving squared distance (0^2+0^2+(-1)^2+1^2 = 2). Hence the edge length in this embedding is (\sqrt{2}).
To obtain a truncated octahedron with unit edge length, we scale all coordinates by (1/\sqrt{2}). The distance from the center ((2.5,2.5,2.5,2.5)) to the vertex (1234) is half the distance between the opposite vertices (1234) and (4321). The vector from the center to (1234) is [ (1-2.5,;2-2.5,;3-2.5,;4-2.5) = (-1.5,,-0.5,,0.5,,1.5), ] with squared length (1.5^2+0.5^2+0.5^2+1.5^2 = 5). Thus the distance from the center to any vertex is (\sqrt{5}) in the natural embedding, and the distance between opposite vertices (1234) and (4321) is (2\sqrt{5} = \sqrt{20}).
After scaling by (1/\sqrt{2}) to make the edges have unit length, the distance between opposite vertices becomes [ \frac{\sqrt{20}}{\sqrt{2}} = \sqrt{10}. ]
The diameter of a convex polyhedron is the maximum Euclidean distance between any two of its vertices. In the truncated octahedron the maximum distance is attained between opposite vertices; the vertices (1234) and (4321) are opposite in the permutohedron. Therefore the diameter is (\sqrt{10}).
[ \boxed{\sqrt{10}} ]