The evolution of the permutahedron

In their seminal paper introducing the theory of random graphs, Erdos and R\'enyi considered the evolution of the structure of a random subgraph of Kₙ as the density increases from 0 to 1, identifying two key points in this evolution -- the percolation threshold, where the order of the largest component seemingly jumps from logarithmic to linear in size, and the connectivity threshold, where the subgraph becomes connected. Similar phenomena have been observed in many other random graph models, and in particular, works of Ajtai, Koml\'os and Szemer\'edi and of Spencer and Erdos determine corresponding thresholds for random subgraphs of the hypercube. We study similar questions on the permutahedron. The permutahedron, like the hypercube, has many different equivalent representations, and arises as a natural object of study in many areas of combinatorics. In particular, as a highly-symmetric simple polytope, like the n-simplex and n-cube, this percolation model naturally generalises the Erdos-R\'enyi random graph and the percolated hypercube. We determine the percolation threshold and the connectivity threshold for random subgraphs of the permutahedron. Along the way we develop a novel graph exploration technique which can be used to find exponentially large clusters after percolation in high-dimensional geometric graphs and we initiate the study of the isoperimetric properties of the permutahedron.