Extension operations for cuts (Q1199597)

Given a set \(V=\{1,2,\dots,n\}\) and a subset \(S\) of \(V\), the cut \(\delta(S)\) is the set of all pairs \((i,j)\), \(1\leq i<j\leq n\), such that \(i\in S\), \(j\in V-S\) or vice versa. The cut \(\delta(S)\) is called \(k\)- uniform if \(| S|=k\) or \(n-k\). The set \({\mathcal C}_ n\) of all the non-negative combinations of cuts is called the cut cone, the set \({\mathcal L}_ n\) of all the integer combinations of cuts is called the cut lattice. The authors consider two extension operations on cuts, namely the antipodal extension \(\text{ant}_ \alpha\) and the \(k\)-extension \(\text{ext}_ k\). These extension operations permit to express and solve questions about the variety of realizations in \({\mathcal C}_ n\). The paper brings several applications, e.g. to the description of the path metric of some graphs and polytopes.