The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i.e. transpositions $(i,i+1)$. The polytope is convex, and symmetric.
From the machine learning perspective we can think the Permutohedron is the "right/correct" embedding of that Cayley graph to $R^n$. No one knows what is the "right/correct" embedding of a Cayley graph in general. The motivation for the question is to try to a bit understand that from the mathematical point of view.
Question 1: Are there any other known "nice" examples of polytopes which correspond to Cayley/Schreier graphs? (By "nice" we can require some symmetry preservation for example, edges of the same length, etc.).
What I have seen so far is the "Truncated cube". And there is a beautiful collection at https://weddslist.com/groups/cayley-plat/index.html (but here are some small groups ).
Question 2: Are there any conditions on Cayley/Schreier graphs which are related to the convexity of the polytope ?
For example if we take just a lattice (Cayley graph of $Z^n$), then it is not the boundary of the convex polytope, or rather, it is, but it is kind of very degenerated. Or in other words there are nodes which are interior for the other nodes - placed in between - not like for the permutohedron.
PS
Here is some example to construct the embedding of that Cayley graph by the popular machine learning package "node2vec": https://www.kaggle.com/code/eugenedurymanov/the-permutohedron-node-embeddings-distance-distr and some comparison with Permutohedron embedding. Thanks to
EUGENE DURYMANOV. Some discussion is planned to be today: https://t.me/sberlogabig/390 everybody welcome.
