Compressed polytopes, initial ideals and complete multipartite graphs
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.
- Unimodular triangulations and coverings of configurations arising from root systems
- Nearly Gorenstein rings arising from finite graphs
- Conic divisorial ideals and non-commutative crepant resolutions of edge rings of complete multipartite graphs
- Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals
- Toric ideals associated with gap-free graphs
- Toric algebra of hypergraphs
- Subdivisions of toric complexes
- Special simplices and Gorenstein toric rings.
- Strongly Koszul edge rings
- Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
- Quadratic initial ideals of root systems
- Toric ideals of series and parallel connections of matroids
- A Gröbner basis characterization for chordal comparability graphs
- Extremal edge polytopes
- Shellability of semigroup rings
- Levelness versus almost Gorensteinness of edge rings of complete multipartite graphs
- Quadratic-monomial generated domains from mixed signed, directed graphs
- Base-sortable matroids and Koszulness of semigroup rings
- The h -vectors of the edge rings of a special family of graphs
- Toric rings of perfectly matchable subgraph polytopes
- Roots of Ehrhart polynomials arising from graphs
- Cohen-Macaulay types of certain edge subrings of bipartite graphs and (generalized) Fuss-Catalan numbers
- Bounded powers of edge ideals: Gorenstein toric rings
- The h-vectors of edge rings of odd cycle compositions
- Face enumeration for split matroid polytopes
- Generalized multiplicities of edge ideals
- Enumerating the faces of split matroid polytopes
- Markov basis and Gröbner basis of Segre-Veronese configuration for testing independence in group-wise selections
- Gröbner bases of nested configurations
This page was built for publication: Compressed polytopes, initial ideals and complete multipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1977661)
