The principal lattice of partitions of a submodular function (Q1174311)

For any finite set \(S\) a function \(f\) is a submodular function on \(S\) if \(f(X)+f(Y) \geq f(X\cup Y)+f(X\cap Y)\) for all \(X,Y\subseteq S\). The author investigates the partition associate of a given submodular function. It is shown that the partitions on which \(f\) reaches a minimum form a lattice. Two algorithms are presented for constructing the principal lattice of partitions. The relationship between constructing the principal lattice of partitions associated with certain bipartite graphs is shown to be related to constructing the principal lattice of partitions corresponding to the rank function of a graph and determining the hybrid rank of a graph.