Polymatroid function
A function [math]f:2^S\rightarrow \mathbb Z_+[/math] is called a polymatroid function on a ground set S if it is monotone increasing and submodular.
If it also satisfies subcardinality, that is, [math]f(X)\le |X|[/math] for every [math]X\subseteq S[/math], then it is the rank function of a matroid. More generally, a k-polymatroid function is a polymatroid function satisfying [math]f(X)\le k|X|[/math] for every [math]X\subseteq S[/math].
Given a polymatroid function f, a vector [math]m \in {\mathbb Z}_+^S[/math] is a matching of f if
- [math]m_e[/math] is even for every [math]e \in S[/math],
- [math]m(X) \leq f(X)[/math] for every [math]X\subseteq S[/math].
If [math]m(S)=f(S)[/math] is also satisfied, then m is a perfect matching.
Matchings in 2-polymatroids
If f is a 2-polymatroid function, then a subset [math]X \subseteq S[/math] is called a matching of f if [math]2 \chi^X[/math] is a matching in the above sense. A matroid [math]M=(S \times \{1,2\},r)[/math] is a representation of the 2-polymatroid function f if [math]r(X \times \{1,2\})=f(X)[/math] for every [math]X \subseteq S[/math]. Note that the representing matroid is not unique. A set [math]X \subseteq S[/math] is a matching of f if and only if [math]X \times \{1,2\}[/math] is an independent set of M.
The minimum size of a matching is denoted by [math]\nu(f)[/math], and [math]\beta(f)[/math] is the minimum number of matchings that cover S. The minimum fractional cover of S by matchings is denoted by [math]\beta^*(f)[/math].
