2016/05/04 by Susan Jowett, Jowett, Susan, Songbao Mo +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1605.01455
arxiv created 2016/05/04 · arxiv updated 2016/05/06
A \em connectivity function on a set E is a function λ:2E→ \mathbb 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.