Compressed polytopes, initial ideals and complete multipartite graphs (Q1977661)

The second hypersimplex of order \(d\) is the convex polytope \(\Delta(2,d)\) which is the convex hull of the configuration \({\mathcal A}_d= \{{\mathbf e}_i+ {\mathbf e}_j\); \(1\leq i< j\leq d\}\) in \(\mathbb{R}^d\), where \({\mathbf e}_i\) is the \(i\)-th unit coordinate vector of \(\mathbb{R}^d\). If \(G\) is a finite connected graph having no loop and no multiple edge on the vertex set \([d]= \{1, 2,\dots, d\}\) with the edge set \(E(G)\), then we write \({\mathcal A}_G\) for the subset \(\{{\mathbf e}_i+ {\mathbf e}_j\in{\mathcal A}_d\); \(\{i,j\}\in E(G)\}\) of \({\mathcal A}_d\). The edge polytope \({\mathcal P}_G\) of \(G\) is the convex hull of \({\mathcal A}_G\) in \(\mathbb{R}^d\). Let \(K[t_1, t_2,\dots, t_d]\) denote the polynomial ring in \(d\) variables over a field \(K\). The affine semigroup ring \(K[G]\) which is generated by all monomials \(t_i t_j\) with \(\{i,j\}\in E(G)\) is called the edge ring of \(G\). When \(G\) is the complete graph on \([d]\), its edge polytope is the second hypersimplex of order \(d\) and its edge ring is the second squarefree Veronese subring of \(K [t_1, t_2,\dots, t_d]\). In the present paper the authors are interested in edge polytopes and edge rings of complete multipartite graphs on \([d]\). Here, a complete multipartite graph on \([d]\) is a finite graph on \([d]\) such that, for a suitable decomposition \([d]= V_1\cup V_2\cup \dots\cup V_n\) of \([d]\), its edge set consists of all \(\{k, \ell\}\) with \(k\in V_i\) and \(\ell\in V_j\) for some \(i\neq j\). First, in section 1, the notion of the algebra of Segre-Veronese type which generalizes both Segre products and Veronese subrings of polynomial rings will be presented. Such algebras are affine semigroup rings which possess squarefree quadratic initial ideals; in particular, these algebras are normal, Cohen-Macaulay and Koszul. The edge ring \(K[G]\) of a finite connected graph \(G\) is an algebra of Segre-Veronese type if and only if \(G\) is a complete multipartite graph. Hence, the edge ring of a complete multipartite graph possesses a squarefree quadratic initial ideal and is normal, Cohen-Macaulay and Koszul. Second, the purpose of section 2 is to discuss the combinatorics on edge polytopes of complete multipartite graphs. It is shown that such a polytope is compressed, i.e., each of its reverse lexicographic triangulations is unimodular. Moreover, the \(f\)-vector, the Ehrhart polynomial together with the normalized volume of the edge polytope of a complete multipartite graph is computed explicitly. It is known that if \(R\) is a homogeneous semigroup ring, then \(R\) is Koszul if and only if its divisor poset (partially ordered set) \(\Sigma_R\) is Cohen-Macaulay. Here \(\Sigma_R\) is the infinite poset consisting of all monomials belonging to \(R\), ordered by divisibility. It is known [\textit{I. Peeva, V. Reiner} and \textit{B. Sturmfels}, Math. Ann. 310, No. 2, 379-393 (1998; Zbl 0893.20048)] that if \(R\) has an initial ideal which is the Stanley-Reisner ideal of a finite poset, then the divisor poset \(\Sigma_R\) is shellable. In Section 3, the problem which complete multipartite graph yields an edge ring having an initial ideal which is the Stanley-Reisner ideal of a finite poset is discussed. It turns out that such a complete multipartite graph is quite rare. However, the authors present the conjecture that the divisor poset of the edge ring of a complete multipartite is always shellable.