Some excluded-minor theorems for a class of polymatroids (Q1316652)

A polymatroid function \(h: 2^ S\rightarrow{\mathbf Z}\) is Boolean if it can be represented in the form \(h(A)=|\bigcup_{a\in A}\phi(A)|\) for a set function \(\phi: S\rightarrow 2^ V\). In this paper the authors develop criteria that help to identify excluded minors for classes of Boolean polymatroids. In particular, they show that there are infinitely many excluded minors (non-Boolean polymatroids such that every proper minor is Boolean), while for Boolean \(k\)-polymatroids (i.e., \(|\phi(A)|\leq k\) for all \(a\in S\)) all excluded minors have size at most \(k+2\), and thus their set of excluded minors is finite. The complete list of eight excluded minors is determined for the class of Boolean 2-polymatroids, which correspond to graphs.