Exact-cover inequality for submodular set functions (${\sum }_{i=1}^{t}f(T_i)\ge kf(T)$)

Suppose $f$ is a normalised set function and a submodular set function, and $T_1,\dots ,T_t\subseteq T$ cover every element of $T$ exactly $k$ times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the monotone set function property nor the nonnegative function property is required.

Proof. Fix an ordering of $T$ and write $a_j=f(P_j)-f(P_{j-1})$ for its successive marginal increments. The chain lower bound for a submodular set function gives $f(T_i)\ge {\sum }_{x_j\in T_i}{a}_j$. Summing counts each $a_j$ exactly $k$ times, and ${\sum }_j{a}_j=f(T)$. Exact coverage matters because the $a_j$ may be negative. For a monotone set function, the same argument also allows each element to occur at least $k$ times.