5
$\begingroup$

We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. transpositions $(i,i+1)$ ).

Any graph is naturally a metric space – with the distance between nodes defined as length of the shortest path between the two nodes. On the other hand we have standard Euclidean distance in $\mathbb{R}^n$. We might hope that for good "embeddings" graph metric is not that much distorted by the embeddings.

The permutohedron embedding is kind of "very good" appearing in many fields of mathematics, so natural to ask:

Question 1: Is there any kind of results that suggests that the permutohedron in in some sense minimal possible distortion embedding of that particular $S_n$ Cayley graph ? (Or may be opposite – there are other embeddings which have less distortion ?) Also we might require embedding to be symmetric (i.e. natural action of $S_n$ on $\mathbb{R}^n$ by permutation matrices preserves graph).

We can ask similar questions for the truncated cube, also for some other polytopes from the beautiful collection at https://weddslist.com/groups/cayley-plat/index.html (but here are some small groups ). And for any other polytope would appear in the answers to the question: What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?

PS

Motivation comes from the machine-learning. Embeddings of everything texts/images/proteins... are highly important in ML. It would be nice to understand more mathematical properties which might distinguish "good embeddings" at least for graphs. Cayley graphs may serve as a kind of model example to understand the general picture. Related question: What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?

PSPS

There are results by T.Tao on distortion, seems to me they are related to similar question for Cayley graph of the Heisenberg group $H_3(Z)$, but in some sense about the continous limit of the graph metric, but not sure at the moment.

https://terrytao.wordpress.com/2018/11/26/embedding-the-heisenberg-group-into-a-bounded-dimensional-euclidean-space-with-optimal-distortion/

Improve this question
$\endgroup$
5
  • $\begingroup$ Do you have some refs on the use of permutahedra in ML? // For the uninitiated, their refined Euler characteristic polynomials, enumerating the topologically distinct faces of these polytopes, govern the algebra of multiplicative inversion of e.g.f.s and, therefore, are intimately related to compositional inversion and the Appell and binomial Sheffer polynomial sequences (e.g., Bernoulli, Hermite, Stirling polynomials of the two kinds). The permuta polynomials can be modeled as surjective mappings. A derivative of the cumulant expansion polynomials gives the permuta polynomials. $\endgroup$
    – Tom Copeland
    Commented Mar 26 at 16:20
  • 1
    $\begingroup$ There has been recent interest in "random sorting networks," which are random shortest paths in the permutohedron graph from one vertex (say the identity element) to its antipode (say the reverse permutation). About 15 years ago, Angel, Holroyd, Romik, and Virág made some beautiful conjectures (now mostly proven, I think) saying that random sorting networks should look like random great circles on the "sphere" that is the permutohedron. See for instance these slides of Duncan Dauvergne: birs.ca/workshops/2019/19w5220/files/Dauvergne.pdf. I think this matches with your heuristics. $\endgroup$
    – Sam Hopkins
    Commented Mar 26 at 18:53
  • $\begingroup$ @TomCopeland thanks for sharing ! Our goal is opposite : apply permutohedron/other math to benchmark/understand ML methods - in particular numerous graph embeddings - DeepWalk, Node2Vec etc... $\endgroup$
    – Alexander Chervov
    Commented Mar 27 at 5:49
  • 1
    $\begingroup$ I merely wanted to accentuate the occurence of the permutahedra, a generalization of an Archimedean polytope, in "many fields of mathematics". More in the refs in OEIS A133314 and A019538. I look forward to responses to this question. (Perhaps this MO-Q is relevant: mathoverflow.net/questions/270070/…) $\endgroup$
    – Tom Copeland
    Commented Mar 27 at 7:17
  • $\begingroup$ Btw, if you have access to a 3-D printer, use veraviana.net/history-of-polyhedra/danielebarbaro to print a 3-D permutahedron (I gotta get one of these). Check out the two physical models in my MO answer mathoverflow.net/questions/32479/…. $\endgroup$
    – Tom Copeland
    Commented Mar 27 at 8:38

0

Reset to default