Retracts and algebraic properties of cut algebras

Abstract

Given a graph G, the cut polytope is the convex hull of its cut vectors. The latter objects are the incidence vectors associated to all cuts of G. Especially motivated by related conjectures of Sturmfels and Sullivant, we study various properties and invariants of the toric algebra of the cut polytope, called its cut algebra. In particular, we characterize those cut algebras which are complete intersections, have linear resolutions or have Castelnuovo Mumford regularity equal to 2. The key idea of our approach is to consider suitable algebra retracts of cut algebras. Additionally, combinatorial retracts of the graph are defined and investigated, which are special minors whose algebraic properties can be compared in a very pleasant way with the corresponding ones of the original graph. Moreover, we discuss several examples and pose new problems as well. (C) 2017 Elsevier Ltd. All rights reserved.