Many faces of symmetric edge polytopes (Q2161212): Difference between revisions

Given a graph \(G = (V, E)\), the associated \textit{symmetric edge polytope} is \[ P(G) \ :=\mathrm{conv} \left\{ \mathbf{e}_v - \mathbf{e}_w, \mathbf{e}_w - \mathbf{e}_v : \, vw \in E \right\} \] where \( \mathbf{e}_v\) denotes a unit vector in \(\mathbf{R}^V\). These polytopes are \textit{reflexive}, i.e., both \(P(G)\) and its dual are lattice polytopes (they have integer vertices), and have interesting combinatorial features. E.g., the zeros of Ehrhart polynomials (integer-point counting functions) of symmetric edge polytopes have been the subjects of recent research. The paper under review highlights the connections of symmetric edge polytopes to two other classes of polytopes appearing in quite different contexts. One such class stems from the Kuramoto model, which describes the behavior of interacting oscillators. These oscillators can naturally be represented by vertices of a graph, with an edge between two oscillators if they interact directly. The symmetric edge polytopes are in this case often called \textit{adjacency polytopes} and have been investigated in particular regarding normalized volume questions. The third class of polytopes arises in the context of the transportation problem. A finite metric space \((X, d)\) gives rise to the \textit{Lipschitz polytope} \[ L(X,d) \ := \ \left\{\mathbf{x} \in \mathbf{R}^X : \, \sum_j x_j = 0, \ x_j - x_k \le d(j,k) \right\}. \] The \textit{Kantorovich-Rubinstein polytope} \(K(X,d)\) is the dual of \(L(X,d)\), sometimes also called the \textit{fundamental polytope} of \((X,d)\). \textit{A. M. Vershik} [Arnold Math. J. 1, No. 1, 75--81 (2015; Zbl 1348.54021)] proposed a combinatorial study of \((X,d)\) via the face structure of \(K(X,d)\). The first theorem of the paper under review is that, for a given graph \(G = (V, E)\) and a subset \(W \subset V\), \[ P(G) \cap \mathbf{R}^W \ = \ K(W, d) \] where on \(W\) we define the metric \(d\) via the distance between any two vertices in \(W\) being equal to the length of a minimal path between them. The authors proceed by applying algebraic-combinatorial methods, in particular Gröbner basis techniques for the associated toric algebras and related unimodular triangulations, to symmetric edge polytopes in their various guises, motivated by the connections and questions in the above-mentioned areas.