Connectivity Functions and Polymatroids

A {\em connectivity function on} a set $E$ is a function $\lambda :2^E\to \mathbb{R}$ such that $\lambda (\mathrm{\varnothing })=0$, that $\lambda (X)=\lambda (E-X)$ for all $X\subseteq E$ and that $\lambda(X\cap Y)+\lambda(X\cup Y)\leq \lambda(X)+\lambda(Y)$forall$X,Y \subseteq E$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. We introduce a notion of duality for polymatroids and prove that every connectivity function is the connectivity function of a self-dual polymatroid. We also prove that every integral connectivity function is the connectivity function of a half-integral self-dual polymatroid.