  In their seminal paper introducing the theory of random graphs, Erd\H{o}s and
R\'{e}nyi considered the evolution of the structure of a random subgraph of
$K_n$ as the density increases from $0$ to $1$, identifying two key points in
this evolution -- the \emph{percolation threshold}, where the order of the
largest component seemingly jumps from logarithmic to linear in size, and the
\emph{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\'{o}s and Szemer\'{e}di and of Spencer and
Erd\H{o}s determine corresponding thresholds for random subgraphs of the
hypercube.
  We study similar questions on the \emph{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
Erd\H{o}s-R\'{e}nyi 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.
