Submodular functions and independence structures (Q2531038)

A function \(\mu\), defined on all subsets of a set \(X\) and taking its values in \(\{0,1,2, \ldots,\infty\}\), is called submodular if it is non-decreasing and \(\mu(A \cup B) + \mu(A \cap B) \le \mu(A) + \mu(B)\) \((A,B\subset X)\). If \(\mathcal E\) is an independence structure on \(X\) then its rank function \(\rho\) \((\rho(A) = \sup\{ \vert E\vert : E\subseteq A, E\in \mathcal E\})\) is submodular. It is shown in \S2 that the submodularity of \(\rho\) is precisely what is required to prove a theorem of \textit{R. Rado} [Q. J. Math., Oxf. Ser. 13, 83--89 (1942; Zbl 0063.06369)]: a family \(\mathfrak A = (A_i : i\in I)\) of subsets of \(X\) has a transversal which lies in the independence structure \(\mathcal E\) if and only if for each finite subset \(J\) of \(I\), \(\rho(\cup_{i\in J} A_i)\ge \vert J\vert\). In \S3 it is shown that the set of integer-valued non-decreasing subadditive functions defined on the subsets of \(X\) form a lattice. A subadditive function is called continuous from below if \(A_i\uparrow A\) implies \(\mu(A_i)\uparrow \mu(A)\); this holds in particular for rank functions. If \(\mu_1\) and \(\mu_2\) are both submodular and continuous from below, then their lattice infimum \(\mu_1\wedge \mu_2\) is continuous from below (though it may not be submodular). Some of these results are now applied. If \(\mu\) is submodular on the subsets of \(X\), then \(\mathcal E(\mu) = \{E\subseteq X : \mu(A)\ge \vert A\vert\) whenever \(A\) is a finite subset of \(\mathcal E\}\) (here, \(\vert A\vert\) is the cardinal number of \(A\), and generally, \(\vert\cdot\vert\) denotes the cardinal function) is an independence structure, and if \(A\subseteq X\) is finite, the rank of \(A\) is \(\mu\wedge \vert\cdot\vert (A)\). An application to transversal theory is also given, generalizing the result that the partial transversals of a family of sets form an independence structure. Next, a theorem of \textit{C. St. J. A. Nash-Williams} is considered [Theory Graphs, Int. Symp. Rome 1966, 263--265 (1968; Zbl 0188.55903)]. Let \((\mathcal E_i : i\in I)\) be a family of independence structures on \(X\), and let \(\mathcal E_i\) have rank function \(\rho_i\). Write \(\mathcal E = \{\cup_{i\in I}\) for each \(i\}\). Then \(\mathcal E\) is a pre-independence structure with rank function \((\sum_{i\in I} \rho_i) \wedge \vert\cdot\vert\). Two other formula for the rank function of \(\mathcal E\)are given. The discussion now turns to graph theory. Let \(\Gamma\) be a directed graph and \(Y\) a set of nodes of \(\Gamma\). Given two sets \(E, F\) of nodes of \(\Gamma\), write \(E\le F\) if every path from ( a node of) \(E\) to (a node of) \(Y\) must contain a node of \(F\). Then \(\le\) is a quasi-order on the sets of nodes of \(\Gamma\). Write \([E] = \{x\in E\): there is a path from \(x\) to \(Y\) which contains no other node of \(E\}\). Then \(\le\) is a partial order of the collection \(\mathcal S\) of sets of the form \([E]\), and moreover, \(\mathcal S\) is a lattice. Take fixed sets \(X\), \(S\) of nodes of \(\Gamma\) such that \(X\le S\), and write, for \(A\subseteq X\), \(\sigma_s(A) = \min\{\vert E\vert, A\le E, E\subseteq S\}\). Then \(\sigma_s\) is submodular on the subsets of \(X\); it induces on \(X\) an independence structure with rank function \(\sigma_s \wedge \vert\cdot\vert\) or simply \(\sigma_s\) when \(X\subseteq S\).