Connectivity Functions and Polymatroids

Original · EN

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