Connectivity functions and polymatroids

A connectivity function on a set E   is a function λ:2E→Rλ:2E→R such that λ(∅)=0λ(∅)=0, that λ(X)=λ(E−X)λ(X)=λ(E−X) for all X⊆EX⊆E and that λ(X∩Y)+λ(X∪Y)≤λ(X)+λ(Y)λ(X∩Y)+λ(X∪Y)≤λ(X)+λ(Y) for all X,Y⊆EX,Y⊆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.