Normal polytopes arising from finite graphs (Q1270039): Difference between revisions

A symmetric relation on a set \(V=\{1,2, \dots, d\}\), i.e. a graph \(G\) possibly with loops but without multiple edges gives rise to a polytope in \(\mathbb{R}^d\) and to a subalgebra of \(K[t_1,t_2, \dots, t_d]\): The edge-polytope \(P_G\) is the convex hull of all points \(\vec e_i +\vec e_j\) in \(\mathbb{R}^d\), where \((i,j)\) is an edge of \(G\), and \(\vec e_i\) denotes the \(i\)th coordinate unit vector; the edge-ring \(K[G]\) is generated by all quadratic monomials \(t_i t_j\) where \((i,j)\) is an edge of \(G\). The main purpose of the article is to describe the normalization of the edge-ring \(K[G]\) explicitly in terms of combinatorics on \(G\), and to give a combinatorial criterion for the edge-polytope \(P_G\) to be normal, i.e. the subalgebra \(K[G]\) to be a normal domain. The main result of this interplay between algebra, geometry and combinatorics is the equivalence of the following conditions: (i) the edge-ring \(K[G]\) is normal (ii) the edge-polytope \(P_G\) possesses a unimodular covering (iii) the graph \(G\) satisfies the odd cycle condition.