Canonical decompositions of symmetric submodular systems (Q760444): Difference between revisions

Consider a pair (E,f) in which E is a finite set and \(f: 2^ E\to R\) is a submodular function. Then, the submodular system (E,f) is called symmetric, if \(f(A)=f(E-A)\) for any \(A\subseteq E\). Any \(C\subseteq E\) such that \(| C| \geq 2\), \(| E-C| \geq 2\) is called a 2-cut of (E,f). By using the set of 2-cuts of (E,f) with a certain minimal value of f and a concept of aggregation associated with a partition of E, a canonical decomposition of the symmetric submodular systems has been defined. This decomposition can be represented by a tree showing the hierarchical structure of the reducible 2-cut aggregations. The theory is a generalization of the decomposition theory of 2-connected graphs developed by Tutte. Other examples of symmetric submodular systems associated to classes of graphs and matroids, for which this decomposition theory can be applied are also given.