Permutahedron

On Quanta, I came across an interesting interview with a mathematician, Federico Ardila, who speaks about the connection between combinatorics and geometry:

When you look at the geometric side of things, suppose, for example, you want to study the permutations (the ways of rearranging a collection of objects). It’s pretty well known that if you have n objects, the number of ways of putting them in a row is n factorial (the product n(n-1)(n-2)…1). So it’s not a very interesting problem to count how many ways there are. But what is their inherent structure?  

The three-dimensional permutahedron, a geometric depiction of the ways to rearrange the numbers 1, 2, 3 and 4. Two permutations are connected by an edge if one can be transformed into the other by swapping two consecutive numbers.     

If you look at when two permutations are related to each other by just swapping two elements, then you start understanding not only how many there are but how are they related to each other. And then, when you say, “OK, let’s take all the permutations, and put an edge between two of them if they’re a swap away,” then you find that you get this beautiful shape that’s a polytope (a geometric object with flat sides). I think it’s completely surprising initially that the inherent relations between permutations are captured in this beautiful polytope called a permutahedron. So all of a sudden you have this geometric model, and you can use tools from polytope theory to try to say new things about permutations. And that polytope has existed for a long time and is very well understood.

The three-dimensional permutahedron, a geometric depiction of the ways to rearrange the numbers 1, 2, 3 and 4. Two permutations are connected by an edge if one can be transformed into the other by swapping two consecutive numbers

This particular structure is in fact a truncated octahedron with fourteen faces comprised of six squares and eight hexagons. There are 24 vertices and 36 edges. Whereas the octahedron is a Platonic solid, the truncated version is an Archimedean solid defined as follows:

In geometry, an Archimedean solid is one of the 13 solids first enumerated by Archimedes. They are the semi-regular convex polyhedra composed of regular polygons meeting in identical vertices, excluding the 5 Platonic solids (which are composed of only one type of polygon) and excluding the prisms and antiprisms. They differ from the Johnson solids, whose regular polygonal faces do not meet in identical vertices. Source.

An example of a Johnson solid would be a triangular bipyramid or dipyramid, a type of hexahedron formed by joining two identical tetrahedra together, the face on one being exactly against a face of the other. The truncated octahedron ends up looking like this:

Interestingly the above shape can, like the cube, tesselate or pack 3-dimensional space. It's by no means obvious but, quite amazingly, this is what happens:

In Mathematics, a permutahedron is an (n−1)-dimensional polytope embedded in an n-dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3, ..., n). Thus the permutahedron of order 4 exists in 3 dimensions, order 3 in two dimensions and order 2 in 1 dimension. A polytope is defined as:

... a geometric object with "flat" sides. It is a generalisation in any number of dimensions of the three-dimensional polyhedron. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. Flat sides mean that the sides of a (k+1)-polytope consist of k-polytopes that may have (k-1)-polytopes in common. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. Source.

All this takes us into complicated areas of mathematics but what's important here is simply to note the link has been forged between two apparently disparate mathematical topics: combinatorics and geometry.